162ms O(n*k^2) JAVA AC solution


  • 0
    W
    public class Solution {
    /*need to improve*/
    public List<List<Integer>> palindromePairs(String[] words) {
        List<List<Integer>> ans = new ArrayList<>();
        Map<String, Integer> wordmap = new HashMap<>();
        Map<String, Integer> reversewordmap = new HashMap<>();
        for(int i=0; i<words.length; i++) {
            wordmap.put(words[i], i);
        }
        /**/
        for (int i=0; i<words.length; i++) {
            StringBuilder sb = new StringBuilder();
            if (wordmap.containsKey("") && isPalindrome(words[i], 0, words[i].length()) && wordmap.get("") != i) {
                ans.add(new ArrayList<Integer>());
                ans.get(ans.size()-1).add(wordmap.get(""));
                ans.get(ans.size()-1).add(i);
            }
            for (int j=words[i].length()-1; j>=0; j--) {
                sb.append(words[i].charAt(j));
                String s = sb.toString();
                if (wordmap.containsKey(s) && isPalindrome(words[i], 0, j) && wordmap.get(s) != i) {
                    ans.add(new ArrayList<Integer>());
                    ans.get(ans.size()-1).add(wordmap.get(s));
                    ans.get(ans.size()-1).add(i);
                }
            }
            reversewordmap.put(sb.toString(), i);
        }
        
        for (int i=0; i<words.length; i++) {
            int len = words[i].length();
            for (int j=0; j<words[i].length(); j++) {
                String s = words[i].substring(0, j);
                if (reversewordmap.containsKey(s) && isPalindrome(words[i], j, len) && reversewordmap.get(s) != i) {
                    ans.add(new ArrayList<Integer>());
                    ans.get(ans.size()-1).add(i);
                    ans.get(ans.size()-1).add(reversewordmap.get(s));
                }
            }
        }
        return ans;
    }
    
    
    private boolean isPalindrome(String word, int start,int end) {
        for (int i=start; i<start + (end - start) / 2; i++) {
            if (word.charAt(i) != word.charAt(end - 1 - i + start))
                return false;
        }
        return true;
    }
    

    }


Log in to reply
 

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