300ms Java solution


  • 0
    B

    Thanks to Nursike's answer, brilliant thought by scanning continuous part of each word, so that only need to check the rest part rather than the whole combination word.

    public List<List<Integer>> palindromePairs(String[] words) {
        List<List<Integer>> ret = new ArrayList<List<Integer>>();
        if (words == null || words.length == 0) return ret;
        int n = words.length - 1;
        Map<String, Integer> wordsMap = new HashMap<String, Integer>(); //  store all words and corresponding indexes
        for (int i = 0; i < words.length; i++) {
            wordsMap.put(words[i], i);
        }
        /** brutal force: TLE */
        // Set<String> palindromes = new HashSet<String>();
        // for (int i = 0; i < n-1; i++) {
            // for (int j = i+1; j < n; j++) {
            //     String frontEnd = words[i] + words[j];
            //     String endFront = words[j] + words[i];
            //     List<Integer> cur;
            //     if (palindromes.contains(frontEnd) || isPalindrome(frontEnd)) {
            //         ret.add(Arrays.asList(new Integer[] {i, j}));
            //         palindromes.add(frontEnd);
            //     }
            //     if (palindromes.contains(endFront) || isPalindrome(endFront)) {
            //         ret.add(Arrays.asList(new Integer[] {j, i}));
            //         palindromes.add(endFront);
            //     }
            // }
        // }
        
        for (int i = 0; i < words.length; i++) {
            /* notice that left/right, only one of them should
             * cover the whole word, otherwise the whole will 
             * be checked twice */
             
            /* if word[i]:(abc)de + word[j]:cba, only need to check whether "de" is palindrome */
            for (int right = 0; right <= words[i].length(); right++) {
                String leftSymmetric = words[i].substring(0, right);
                Integer j = wordsMap.get(new StringBuffer(leftSymmetric).reverse().toString());
                if (j == null || i == j) {
                    continue;
                }
                if (isPalindrome(words[i].substring(right))) {
                    ret.add(Arrays.asList(new Integer[] {i, j}));
                }
            }
            /* if word[j]:ed + word[i]:abc(de), only need to check whether "abc" is palindrome */
            for (int left = words[i].length(); left >= 1; left--) { //  here left >= 1 because the whole word has been checked
                                                                    //  in the right part
                String rightSymmetric = words[i].substring(left);
                Integer j = wordsMap.get(new StringBuffer(rightSymmetric).reverse().toString());
                if (j == null || i == j) {
                    continue;
                }
                if (isPalindrome(words[i].substring(0, left))) {
                    ret.add(Arrays.asList(new Integer[] {j, i}));
                }
            }
            
        }
        return ret;
    }
    private boolean isPalindrome(String word) {
        for (int i = 0, j = word.length()-1; i < j; i++, j--) {
            if (word.charAt(i) != word.charAt(j)) {
                return false;
            }
        }
        return true;
    }
    

  • 0
    This post is deleted!

  • 0

    this maybe have duplicate arrarylist so need to use the HashSet to store then toArrayList


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.