KMP based solution, beats 83%, 128ms, word + # + reverse trick


  • 0
    D
    public class Solution {
        private Map<String, Integer> strIndexMap = new HashMap<>();
    
        class WordAnalysis {
            String word;
            String reverseWord;
            int index;
            String leftword;
            String rightword;
            int[] leftpi;
            int[] rightpi;
            List<List<Integer>> leftSide = new ArrayList<>();
            List<List<Integer>> rightSide = new ArrayList<>();
            public WordAnalysis(String word, int index) {
                this.word = word;
                this.index = index;
                reverseWord = reverse(word);
                this.leftword = word + "#" + reverseWord;
                this.rightword = reverseWord + "#" + word;
                initleftpi();
                initrightpi();
                analyzeleft();
                analyzeright();
            }
            private String reverse(String word) {
                StringBuffer sb = new StringBuffer();
                for (int i = 0; i < word.length(); i++) {
                    sb.append(word.charAt(word.length() - 1 - i));
                }
                return sb.toString();
            }
            private void initleftpi() {
                leftpi = new int[leftword.length()];
                calcpi(leftword, leftpi);
            }
            private void initrightpi() {
                rightpi = new int[rightword.length()];
                calcpi(rightword, rightpi);
            }
            private void calcpi(String word, int[] pi) {
                pi[0] = 0;
                for (int i = 1; i < pi.length; i++) {
                    int j = i - 1;
                    while (j >= 0 && word.charAt(pi[j]) != word.charAt(i)) {
                        j = pi[j] - 1;
                    }
                    pi[i] = j >= 0 ? pi[j] + 1 : 0;
                }
            }
            private void analyzeleft() {
                int prefixEndIndex = leftword.length() - 1;
                while (prefixEndIndex >= 0 && leftpi[prefixEndIndex] >= 0) {
                    String leftCand = reverseWord.substring(0, reverseWord.length() - leftpi[prefixEndIndex]);
                    if (strIndexMap.containsKey(leftCand) && strIndexMap.get(leftCand) != index) {
                        List<Integer> left = new ArrayList<>();
                        left.add(strIndexMap.get(leftCand));
                        left.add(index);
                        leftSide.add(left);
                    }
                    prefixEndIndex = leftpi[prefixEndIndex] - 1;
                }
            }
            private void analyzeright() {
                int prefixEndIndex = rightword.length() - 1;
                while (prefixEndIndex >= 0 && rightpi[prefixEndIndex] >= 0) {
                    int tailLen = word.length() - rightpi[prefixEndIndex];
                    String rightCand = tailLen == 0 ? "" : reverseWord.substring(word.length() - tailLen);
                    if (strIndexMap.containsKey(rightCand) && strIndexMap.get(rightCand) != index) {
                        List<Integer> right = new ArrayList<>();
                        right.add(index);
                        right.add(strIndexMap.get(rightCand));
                        rightSide.add(right);
                    }
                    prefixEndIndex = rightpi[prefixEndIndex] - 1;
                }
            }
        }
    
        public List<List<Integer>> palindromePairs(String[] words) {
            if (words == null || words.length <= 1) {
                return new ArrayList<>();
            }
            for (int i = 0; i < words.length; i++) {
                strIndexMap.put(words[i], i);
            }
            WordAnalysis[] wordAnalysis = new WordAnalysis[words.length];
            for (int i = 0; i < words.length; i++) {
                if (!words.equals("")) {
                    wordAnalysis[i] = new WordAnalysis(words[i], i);
                }
            }
            Set<List<Integer>> ret = new HashSet<>();
            for (WordAnalysis wanalysis : wordAnalysis) {
                ret.addAll(wanalysis.leftSide);
                ret.addAll(wanalysis.rightSide);
            }
            return new ArrayList<>(ret);
        }
    }
    

Log in to reply
 

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