Java solution with logic


  • 0
    V
    1. Add all words( reversed ) to a map.
    2. loop each word from given list : for each word split it at all levels foe eg. :
      if cbab is the word, then split levels are cbab:"", c:bab, cb:ab, cba:b . In tis example you can see that in c:bab - if bab is a palindrome and if c is in our map, then it forms a pair.
      We need to check the other way around also because say "kk:s", if kk' is a palindrome and s is in map, then s+kks is a palindrome pair.
    public class Solution {
        public List<List<Integer>> palindromePairs(String[] words) {
            HashSet<List<Integer>> pairs = new HashSet<List<Integer>>();
            if(words == null || words.length == 0) return new ArrayList<>(pairs);
            
            int len = words.length;
            Map<String, Integer> map = new HashMap<String, Integer>();
            
            for(int i=0; i<len; i++) {
                map.put(new StringBuilder(words[i]).reverse().toString(), i);
            }
            
            for(int i=0; i<len; i++) {
                String word = words[i];
                int wlen = word.length();
                int s = 0;
                while(s <= wlen) {
                    String first = word.substring(0, s);
                    String second = word.substring(s);
                    //System.out.println(first + ":"+ second);
                    
                    if(map.containsKey(first) && isPalindrome(second)) {
                        int index = map.get(first);
                        if(i != index) pairs.add(new ArrayList<Integer>(Arrays.asList(i, index)));
                    }
                    
                    if(map.containsKey(second) && isPalindrome(first)) {
                        int index = map.get(second);
                        if(i != index) pairs.add(new ArrayList<Integer>(Arrays.asList(index, i)));
                    }
                    
                    s++;
                }
            }
            
            return new ArrayList<>(pairs);
        }
        
        
        private boolean isPalindrome(String s) {
            int len = s.length();
            for(int i=0,j=len-1;i<len/2;i++,j--){
                if(s.charAt(i) != s.charAt(j)) return false;
            }
            return true;
        }
    }
    

Log in to reply
 

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