美文网首页
LeetCode 336. Palindrome Pairs

LeetCode 336. Palindrome Pairs

作者: manayuan | 来源:发表于2018-11-06 15:02 被阅读0次
    • 对每个word,如果它翻转过来之后[:n]或者[n:]和map中已有的key相同,且剩下的一部分是palindrome,那么它们能组成palindrome
    class Solution {
        public List<List<Integer>> palindromePairs(String[] words) {
            List<List<Integer>> pairs = new LinkedList<>();
            if (words == null) return pairs;
            HashMap<String, Integer> map = new HashMap<>();
            for (int i = 0; i < words.length; ++ i) map.put(words[i], i);
            for (int i = 0; i < words.length; ++ i) {
                int l = 0, r = 0;
                while (l <= r) {
                    String s = words[i].substring(l, r);
                    Integer j = map.get(new StringBuilder(s).reverse().toString());
                    if (j != null && i != j && isPalindrome(words[i].substring(l == 0 ? r : 0, l == 0 ? words[i].length() : l)))
                        pairs.add(Arrays.asList(l == 0 ? new Integer[]{i, j} : new Integer[]{j, i}));
                    if (r < words[i].length()) ++r;
                    else ++l;
                }
            }
            return pairs;
        }
    
        private boolean isPalindrome(String s) {
            for (int i = 0; i < s.length()/2; ++ i)
                if (s.charAt(i) != s.charAt(s.length()-1-i))
                    return false;
            return true;
        }
    }
    
    • 用trie实现,就不用两次遍历这个word判断是否存在在map中

    相关文章

      网友评论

          本文标题:LeetCode 336. Palindrome Pairs

          本文链接:https://www.haomeiwen.com/subject/owduxqtx.html