美文网首页
Palindrome Pairs

Palindrome Pairs

作者: BLUE_fdf9 | 来源:发表于2018-09-23 01:05 被阅读0次

题目
Given a list of unique words, find all pairs of distinct indices (i, j) in the given list, so that the concatenation of the two words, i.e. words[i] + words[j] is a palindrome.

答案

class Solution {
    public List<List<Integer>> palindromePairs(String[] words) {
        List<List<Integer>> list = new ArrayList<>();
        Map<String, Integer> map = new HashMap<>();
        Set<List<Integer>> dup = new HashSet<>();
        for(int i = 0; i < words.length; i++) {
            StringBuilder sb = new StringBuilder(words[i]);
            String reversed = sb.reverse().toString();
            map.put(reversed, i);
        }

        for(int i = 0; i < words.length; i++) {
            for(int j = 0; j < words[i].length() + 1; j++) {
                String left = words[i].substring(0, j);
                String right = words[i].substring(j);

                Integer left_idx = map.get(left);
                if(left_idx != null && left_idx != i && is_pal(right)) {
                    List<Integer> l = Arrays.asList(new Integer[]{i, left_idx});
                    if(!dup.contains(l)) {
                        dup.add(l);
                        list.add(l);
                    }
                }

                Integer right_idx = map.get(right);
                if(right_idx != null && right_idx != i && is_pal(left)) {
                    List<Integer> l = Arrays.asList(new Integer[]{right_idx, i});
                    if(!dup.contains(l)) {
                        dup.add(l);
                        list.add(l);
                    }
                }

            }
        }

        return list;
    }

    public boolean is_pal(String s) {
        int l = 0, r = s.length() - 1;
        while(l < r) {
            if(s.charAt(l++) != s.charAt(r--)) return false;
        }
        return true;
    }
}

相关文章

网友评论

      本文标题:Palindrome Pairs

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