150 ms 45 lines JAVA solution


  • 133
    M
    public List<List<Integer>> palindromePairs(String[] words) {
        List<List<Integer>> ret = new ArrayList<>(); 
        if (words == null || words.length < 2) return ret;
        Map<String, Integer> map = new HashMap<String, Integer>();
        for (int i=0; i<words.length; i++) map.put(words[i], i);
        for (int i=0; i<words.length; i++) {
            // System.out.println(words[i]);
            for (int j=0; j<=words[i].length(); j++) { // notice it should be "j <= words[i].length()"
                String str1 = words[i].substring(0, j);
                String str2 = words[i].substring(j);
                if (isPalindrome(str1)) {
                    String str2rvs = new StringBuilder(str2).reverse().toString();
                    if (map.containsKey(str2rvs) && map.get(str2rvs) != i) {
                        List<Integer> list = new ArrayList<Integer>();
                        list.add(map.get(str2rvs));
                        list.add(i);
                        ret.add(list);
                        // System.out.printf("isPal(str1): %s\n", list.toString());
                    }
                }
                if (isPalindrome(str2)) {
                    String str1rvs = new StringBuilder(str1).reverse().toString();
                    // check "str.length() != 0" to avoid duplicates
                    if (map.containsKey(str1rvs) && map.get(str1rvs) != i && str2.length()!=0) { 
                        List<Integer> list = new ArrayList<Integer>();
                        list.add(i);
                        list.add(map.get(str1rvs));
                        ret.add(list);
                        // System.out.printf("isPal(str2): %s\n", list.toString());
                    }
                }
            }
        }
        return ret;
    }
    
    private boolean isPalindrome(String str) {
        int left = 0;
        int right = str.length() - 1;
        while (left <= right) {
            if (str.charAt(left++) !=  str.charAt(right--)) return false;
        }
        return true;
    }
    
    1. The <= in for (int j=0; j<=words[i].length(); j++) is aimed to handle empty string in the input. Consider the test case of ["a", ""];

    2. Since we now use <= in for (int j=0; j<=words[i].length(); j++) instead of <. There may be duplicates in the output (consider test case ["abcd", "dcba"]). Therefore I put a str2.length()!=0 to avoid duplicates.

    Another way to avoid duplicates is to use Set<List<Integer>> ret = new HashSet<>(); and return new ArrayList<>(ret);


  • 1
    S

    Good!!! Simple and easy to understand


  • 0
    B

    this is clear!


  • 4
    B

    Is the time complexity O(m * n ^ 2) where m is the length of the list and the n is the length of the word.


  • 15
    Y

    Very clean solution overall. But I found your two if statements repeating themselves. Here is some modification suggestions. We can use another function, I call it addPair here and pass in necessary info. if(str2.length() != 0) is used to avoid duplicates. And we reverse the order of str1 and str2 so that both of the cases will be considered.

    public List<List<Integer>> palindromePairs(String[] words) {
        List<List<Integer>> res = new ArrayList<>(); 
        if (words == null || words.length < 2) {
            return res;
        }
        Map<String, Integer> map = new HashMap<String, Integer>();
        for (int i = 0; i < words.length; i++) {
            map.put(words[i], i);
        }
        for (int i = 0; i < words.length; i++) {
            for (int j = 0; j <= words[i].length(); j++) {
                String str1 = words[i].substring(0, j);
                String str2 = words[i].substring(j);
                addPair(map, res, str1, str2, i, false);
                if(str2.length() != 0) {
                    addPair(map, res, str2, str1, i, true);
                }
            }
        }
        return res;
    }
    

    Here is the addPair function

    private void addPair(Map<String, Integer> map, List<List<Integer>> res, String str1, String str2, int index, boolean reverse) {
        if (isPalindrome(str1)) {
            String str2rev = new StringBuilder(str2).reverse().toString();
            if (map.containsKey(str2rev) && map.get(str2rev) != index) {
                List<Integer> list = new ArrayList<>();
                if(!reverse) {
                    list.add(map.get(str2rev));
                    list.add(index);
                } else {
                    list.add(index);
                    list.add(map.get(str2rev));
                }
                res.add(list);
            }
        }
    }

  • 2
    M

    @XiaoboZhang1991 I think you are right.


  • 0
    2

    if the length of each word is much larger than thecapacity of words[], whether contacting two
    words is easier?


  • 8
    H

    Thanks for sharing your code!

    Based on your code, I made it more concise, and a little bit faster. 142 ms.

    public class Solution {
        public List<List<Integer>> palindromePairs(String[] words) {
            List<List<Integer>> ret = new ArrayList<>(); 
            if (words == null || words.length < 2) return ret;
            Map<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++) {
                for (int j=0; j<=words[i].length(); j++) { // notice it should be "j <= words[i].length()"
                    String str1 = words[i].substring(0, j);
                    String str2 = words[i].substring(j);
                    if (isPalindrome(str1)) {
                        String str2rvs = new StringBuilder(str2).reverse().toString();
                        if (map.getOrDefault(str2rvs, i) != i) {
                            ret.add(Arrays.asList(map.get(str2rvs), i));
                        }
                    }
                    if (isPalindrome(str2) && str2.length() != 0) {
                        String str1rvs = new StringBuilder(str1).reverse().toString();
                        // check "str.length() != 0" to avoid duplicates
                        if (map.getOrDefault(str1rvs, i) != i) { 
                            ret.add(Arrays.asList(i, map.get(str1rvs)));
                        }
                    }
                }
            }
            return ret;
        }
        
        private boolean isPalindrome(String str) {
            for (int l = 0, r = str.length() - 1; l <= r; l ++, r --) {
                if (str.charAt(l) != str.charAt(r)) {
                    return false;
                }
            }
            return true;
        }
    }

  • 4
    Z

    Thanks for your sharing.
    Below is C++ implemention of your idea.

    class Solution {
        bool isPalindrome(const string& s){
            if(s.empty()) return true;
            for(int i = 0, j = s.size()-1; i < j; ++i, --j){
                if(s[i] != s[j]) return false;
            }
            return true;
        }
    public:
        vector<vector<int>> palindromePairs(vector<string>& words) {
            vector<vector<int>> res;
            if(words.size() < 2) return res;
            unordered_map<string, int> str2idx;
            for(int i = 0; i < words.size(); ++i){
                str2idx[words[i]] = i;
            }
            for(int i = 0; i < words.size(); ++i){
                string word = words[i];
                for(int len = 0; len <= word.size(); ++len){
                    string prefix = word.substr(0, len);
                    string suffix = word.substr(len);
                    if(isPalindrome(prefix)){
                        string tmp(suffix.rbegin(), suffix.rend());
                        if(str2idx.count(tmp) && str2idx[tmp] != i){
                            res.push_back({str2idx[tmp], i});
                        }
                    }
                    if(isPalindrome(suffix)){
                        string tmp(prefix.rbegin(), prefix.rend());
                        if(str2idx.count(tmp) && str2idx[tmp] != i && !suffix.empty()){
                            res.push_back({i, str2idx[tmp]});
                        }
                    }
                }
            }
            return res;
        }
    };

  • 0

    @XiaoboZhang1991 I think so.


  • 0

    Good idea. But if the given array has duplicates?


  • 0
    H

    @XiaoboZhang1991 said in 150 ms 45 lines JAVA solution:

    time

    I second that.


  • 0
    R

    what if the words have multiple entries of the same word. The map can have only 1 key for them and that will probable have the last index of the word in the array


  • 0
    J

    @Zhoujingjin the use of reverse iterator is really smart! I never thought of that, thanks!


  • 0
    T

    For

    List<Integer> list = new ArrayList<Integer>();
                        list.add(map.get(str2rvs));
                        list.add(i);
    

    This part can be simplified to one line:

    List<Integer> list = Arrays.asList(map.get(str2rvs), i);
    

  • 0
    K

    it's really clear, thanks a lot!


  • 0
    I

    Brilliant idea!
    Minor improvement, when pre-process, we can put reverse of words[i] into the map. Thus, during the loop, we don't have to reverse str1 or str2. This way, the running time improves to 127ms.


  • 0

    @TangHao1987 Agreed! Nice solution with much room to be more readable tough. And it's a little tricky to remember to de-duplicate in that way. Thanks for sharing!

        // From naive O(nnk) to O(nkk) time.
        public List<List<Integer>> palindromePairs(String[] words) {
            Map<String, Integer> map = new HashMap<>();
            for (int i = 0; i < words.length; i++) map.put(words[i], i);
            
            List<List<Integer>> ret = new ArrayList<>();
            for (int i = 0; i < words.length; i++) {
                for (int j = 0; j <= words[i].length(); j++) { // Note j=[0..len]: s1="",s2=word -> s1=word,s2=""
                    String s1 = words[i].substring(0, j), s2 = words[i].substring(j);
                    if (isPalindrome(s1)) { // word2 + s1 + s2 is palindrome
                        String t = new StringBuilder(s2).reverse().toString();
                        if (map.getOrDefault(t, i) != i) ret.add(Arrays.asList(map.get(t), i));
                    }
                    if (isPalindrome(s2) && !s2.isEmpty()) { // s1 + s2 + word2 is palindrome (avoid duplicate)
                        String t = new StringBuilder(s1).reverse().toString();
                        if (map.getOrDefault(t, i) != i) ret.add(Arrays.asList(i, map.get(t)));
                    }
                }
            }
            return ret;
        }
    

  • 0
    S

    @xyao01 If it has duplicates, we can store a map like <String, List<Integer>>


  • -1
    S

    I can't understand why does it need to make sure str1 or str2 to be palindrome?


Log in to reply
 

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