JavaInterview JavaInterview
首页
指南
分类
标签
归档
  • CSDN (opens new window)
  • 文档集合 (opens new window)
  • 系统架构 (opens new window)
  • 微信号 (opens new window)
  • 公众号 (opens new window)

『Java面试+Java学习』
首页
指南
分类
标签
归档
  • CSDN (opens new window)
  • 文档集合 (opens new window)
  • 系统架构 (opens new window)
  • 微信号 (opens new window)
  • 公众号 (opens new window)
  • 指南
  • 简历

  • Java

  • 面试

  • 算法

  • algorithm
  • leetcode
JavaInterview.cn
2022-07-23
目录

回文对Java

文章发布较早,内容可能过时,阅读注意甄别。

# 题目

给定一组 互不相同 的单词, 找出所有 不同 的索引对 (i, j),使得列表中的两个单词, words[i] + words[j] ,可拼接成回文串。

示例 1:

输入:words = ["abcd","dcba","lls","s","sssll"]
输出:[[0,1],[1,0],[3,2],[2,4]] 
解释:可拼接成的回文串为 ["dcbaabcd","abcddcba","slls","llssssll"]

示例 2:

输入:words = ["bat","tab","cat"]
输出:[[0,1],[1,0]] 
解释:可拼接成的回文串为 ["battab","tabbat"]

示例 3:

输入:words = ["a",""]
输出:[[0,1],[1,0]]

提示:

  • 1 <= words.length <= 5000
  • 0 <= words[i].length <= 300
  • words[i] 由小写英文字母组成

# 思路

建立节点Node

static class Node {
    char c;
    Map<String, Integer> idx = new HashMap<>();
    Map<Character, Node> children = new HashMap<>();

# 解法


import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Solution {

    public List<List<Integer>> palindromePairs(String[] words) {
        Node head = new Node('\0');
        for (int i = 0; i < words.length; i++) {
            head.put(words[i], 0, i);
        }
        List<List<Integer>> result = new ArrayList<>();
        for (int i = 0; i < words.length; i++) {
            check(result, head, words[i], i);
        }
        return result;
    }

    private void check(List<List<Integer>> result, Node node, String word, int wordIndex) {
        if (!node.idx.isEmpty() && isPalindrome(word, 0, word.length() - 1)) {
            for (Integer index : node.idx.values()) {
                if (wordIndex != index) {
                    result.add(Arrays.asList(index, wordIndex));
                }
            }
        }
        for (int i = word.length() - 1; i >= 0; i--) {
            char c = word.charAt(i);
            Node child = node.children.get(c);
            if (child == null) {
                return;
            }
            if (!child.idx.isEmpty() && isPalindrome(word, 0, i - 1)) {
                for (Integer index : child.idx.values()) {
                    if (wordIndex != index) {
                        result.add(Arrays.asList(index, wordIndex));
                    }
                }
            }
            node = child;
        }
        Collection<Node> children = node.children.values();
        while (!children.isEmpty()) {
            List<Node> next = new ArrayList<>();
            for (Node child : children) {
                next.addAll(child.children.values());
                for (Map.Entry<String, Integer> entry : child.idx.entrySet()) {
                    if (isPalindrome(entry.getKey(), word.length(), entry.getKey().length() - 1)) {
                        result.add(Arrays.asList(entry.getValue(), wordIndex));
                    }
                }
            }
            children = next;
        }
    }

    private boolean isPalindrome(String str, int start, int end) {
        while (start < end) {
            if (str.charAt(start++) != str.charAt(end--)) {
                return false;
            }
        }
        return true;
    }

    static class Node {
        char c;
        Map<String, Integer> idx = new HashMap<>();
        Map<Character, Node> children = new HashMap<>();

        public Node(final char c) {
            this.c = c;
        }

        void put(String str, int i, int index) {
            if (i == str.length()) {
                idx.put(str, index);
                return;
            }
            char sc = str.charAt(i);
            Node child = children.computeIfAbsent(sc, t -> new Node(sc));
            child.put(str, i + 1, index);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89

# 总结

  • 分析出几种情况,然后分别对各个情况实现
微信 支付宝
最近更新
01
1637. 两点之间不包含任何点的最宽垂直区域 Java
06-26
02
1636. 按照频率将数组升序排序 Java
06-26
03
1638. 统计只差一个字符的子串数目 Java
06-26
更多文章>
Theme by Vdoing | Copyright © 2019-2025 JavaInterview.cn
  • 跟随系统
  • 浅色模式
  • 深色模式
  • 阅读模式