The Easy-to-unserstand JAVA Solution


  • 46
    I

    There are several cases to be considered that isPalindrome(s1 + s2):

    Case1: If s1 is a blank string, then for any string that is palindrome s2, s1+s2 and s2+s1 are palindrome.

    Case 2: If s2 is the reversing string of s1, then s1+s2 and s2+s1 are palindrome.

    Case 3: If s1[0:cut] is palindrome and there exists s2 is the reversing string of s1[cut+1:] , then s2+s1 is palindrome.

    Case 4: Similiar to case3. If s1[cut+1: ] is palindrome and there exists s2 is the reversing string of s1[0:cut] , then s1+s2 is palindrome.

    To make the search faster, build a HashMap to store the String-idx pairs.

    My code:

    public class Solution {
    public List<List<Integer>> palindromePairs(String[] words) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        if(words == null || words.length == 0){
            return res;
        }
        //build the map save the key-val pairs: String - idx
        HashMap<String, Integer> map = new HashMap<>();
        for(int i = 0; i < words.length; i++){
            map.put(words[i], i);
        }
        
        //special cases: "" can be combine with any palindrome string
        if(map.containsKey("")){
            int blankIdx = map.get("");
            for(int i = 0; i < words.length; i++){
                if(isPalindrome(words[i])){
                    if(i == blankIdx) continue;
                    res.add(Arrays.asList(blankIdx, i));
                    res.add(Arrays.asList(i, blankIdx));
                }
            }
        }
        
        //find all string and reverse string pairs
        for(int i = 0; i < words.length; i++){
            String cur_r = reverseStr(words[i]);
            if(map.containsKey(cur_r)){
                int found = map.get(cur_r);
                if(found == i) continue;
                res.add(Arrays.asList(i, found));
            }
        }
        
        //find the pair s1, s2 that 
        //case1 : s1[0:cut] is palindrome and s1[cut+1:] = reverse(s2) => (s2, s1)
        //case2 : s1[cut+1:] is palindrome and s1[0:cut] = reverse(s2) => (s1, s2)
        for(int i = 0; i < words.length; i++){
            String cur = words[i];
            for(int cut = 1; cut < cur.length(); cut++){
                if(isPalindrome(cur.substring(0, cut))){
                    String cut_r = reverseStr(cur.substring(cut));
                    if(map.containsKey(cut_r)){
                        int found = map.get(cut_r);
                        if(found == i) continue;
                        res.add(Arrays.asList(found, i));
                    }
                }
                if(isPalindrome(cur.substring(cut))){
                    String cut_r = reverseStr(cur.substring(0, cut));
                    if(map.containsKey(cut_r)){
                        int found = map.get(cut_r);
                        if(found == i) continue;
                        res.add(Arrays.asList(i, found));
                    }
                }
            }
        }
        
        return res;
    }
    
    public String reverseStr(String str){
        StringBuilder sb= new StringBuilder(str);
        return sb.reverse().toString();
    }
    
    public boolean isPalindrome(String s){
        int i = 0;
        int j = s.length() - 1;
        while(i <= j){
            if(s.charAt(i) != s.charAt(j)){
                return false;
            }
            i++;
            j--;
        }
        return true;
    }
    

    }


  • 0
    S
    This post is deleted!

  • 0
    Y

    How can you deal with duplicate pairs generated by different cases, eg. cases both fulfil case2 and case3, in the result s2+s1 will be added twice.


  • 0
    This post is deleted!

  • 0
    Y

    for case 3, 4, how about to maintain a map of reverse word and index, check if the substring is in this map and get the corresponding index out, instead to reverse each and them and check the original map?


  • 0
    Y

    Here's my Python version of this solution:

    class Solution(object):

    def palindromePairs(self, words):
        
        if not words: return []
        
        isPalindrome = lambda x: x == x[::-1]
        
        d = {}
        for i in range(len(words)):
            d[words[i]] = i
        
        res = []
        
        # If "" in words, add all palindrome words into res
        if "" in d:
            blankIndex = d[""]
            for i in range(len(words)):
                if i != blankIndex and isPalindrome(words[i]):
                    res.append([blankIndex, i])
                    res.append([i, blankIndex])
        
        # For every word in words, if word[::-1] is also in words, then [word, word[::-1]] makes a palindrome pair
        for i in range(len(words)):
            revWord = words[i][::-1]
            if revWord in d and d[revWord] != i:
                res.append([i, d[revWord]])
        
        # If s1[:cut] is a palindrome, and s1[cut:][::-1] in d, then (s2, s1) is a palindrome pair. If s1[cut:] is a palindrome and s1[cut:][::-1] in d, then (s1, s2) is a palindrome pair.
        for i in range(len(words)):
            cur_word = words[i]
            for cut in range(1, len(cur_word)):
                cut_l = cur_word[:cut]
                cut_r = cur_word[cut:]
                rev_cut_l = cut_l[::-1]
                rev_cut_r = cut_r[::-1]
                
                if isPalindrome(cut_l):
                    if rev_cut_r in d and rev_cut_r != i:
                        res.append([d[rev_cut_r], i])
                
                if isPalindrome(cut_r):
                    if rev_cut_l in d and rev_cut_l != i:
                        res.append([i, d[rev_cut_l]])
        return res

  • 0
    M

    Hey, I simplify your code by cutting the first loop in your code and modify some in your 2nd loop.

    public class Solution {
        public List<List<Integer>> palindromePairs(String[] words) {
            Map<String,Integer> map = new HashMap<String,Integer>();
            for(int i = 0; i < words.length; i++){
                map.put(words[i],i);
            }
            List<List<Integer>> res = new LinkedList<List<Integer>>();
            for(int i = 0; i < words.length; i++){
                String curStr = words[i];
                for(int split = 0; split < curStr.length(); split++){
                    
                    // left part : curStr.substring(0,split) ... 
                    // right part : curStr.substring(split, curString.length())
                    String left = curStr.substring(0,split), right = curStr.substring(split, curStr.length());
                    String r_right = reverse(right), r_left = reverse(left);
                    
                    if(split == 0){
                        // "abccba"
                        if(isParlindrome(right)){
                            // curStr is parlindrome
                            if(map.containsKey("")){
                                List<Integer> list1 = new LinkedList<Integer>();
                                list1.add(map.get(""));
                                list1.add(i);
                                res.add(list1);
                                List<Integer> list2 = new LinkedList<Integer>();
                                list2.add(i);
                                list2.add(map.get(""));
                                res.add(list2);
                            }
                        }else{
                            if(map.containsKey(r_right)){
                                List<Integer> list = new LinkedList<Integer>();
                                list.add(i);
                                list.add(map.get(r_right));
                                res.add(list);
                            }
                        }
                    }else{
                        if(isParlindrome(left) && map.containsKey(r_right) && map.get(r_right) != i){
                            
                            List<Integer> list = new LinkedList<Integer>();
                            list.add(map.get(r_right));
                            list.add(i);
                            res.add(list);
                        }
                        if(isParlindrome(right) && map.containsKey(r_left) && map.get(r_left) != i){
                            List<Integer> list = new LinkedList<Integer>();
                            list.add(i);
                            list.add(map.get(r_left));
                            res.add(list);
                        }
                    }
                }
            }
            return res;
        }
        public String reverse(String str){
        	int left = 0, right = str.length() - 1;
        	char[] chars = str.toCharArray();
    
        	while(left < right){
        		char tmp = chars[left];
        		chars[left] = chars[right];
        		chars[right] = tmp;
        		left++;
        		right--;
        	}
        	return String.valueOf(chars);
        }
        public boolean isParlindrome(String str){
            if(str.equals("")){
                return true;
            }
        	int left = 0, right = str.length() - 1;
        	while(left <= right){
        		if(str.charAt(left) != str.charAt(right)){
        			return false;
        		}
        		left++;
        		right--;
        	}
        	return true;
        }
    }

  • 0
    B

    What is the time complexity of this solution ? O(k), where k is the total number of characters ?


  • 0
    B

    @isabel2 said in The Easy-to-unserstand JAVA Solution:
    Shouldn't cut start from 0 here:
    for(int cut = 1; cut < cur.length(); cut++)

    Eg: s1="abcd" and s2="dcb", then s2+s1 = "dcbabcd" is a palindrome.


  • 0
    J

    @bhanuverma it's O(n*k^2), where n is the number of strings in words[]


Log in to reply
 

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