[143ms] any improvement on this code?


  • 0
    N
    public class Solution {
        public List<List<Integer>> palindromePairs(String[] words) {
            Map<String,List<Integer>> map = initMap(words);  
            List<List<Integer>> allPairs = new ArrayList<>();
            for(int i = 0; i < words.length; i++) {
                findAllPairs(allPairs,map,words,i);
            }
            return allPairs;
        }
        void findAllPairs(List<List<Integer>> allPairs, Map<String,List<Integer>> map, String[] words, int i) {
            String target = words[i];
            for(int len = 1; len <= target.length(); len++) {
                String p1 = target.substring(0,len);
                String p2 = target.substring(len, target.length());
                if (isPalin(p1)) {
                    String rp2 = reverse(p2);
                    if(map.containsKey(rp2)) {
                        if(rp2.length() == 0) {
                            makePairs(allPairs,i,map.get(rp2), true);
                            makePairs(allPairs,i,map.get(rp2), false);
                        } else {
                            makePairs(allPairs,i,map.get(rp2), false);
                        }
                    }
                }
                if (isPalin(p2)) {
                    String rp1 = reverse(p1);
                    if (map.containsKey(rp1)) {
                        makePairs(allPairs,i,map.get(rp1), true);
                    }
                }        
            }
        }
        void makePairs(List<List<Integer>> allPairs, int i, List<Integer> m, boolean isLeft) {
                for(int mm : m) {
                    if(i != mm) {
                        if(isLeft) {
                            allPairs.add(Arrays.asList(i,mm));
                        } else {
                            allPairs.add(Arrays.asList(mm,i));
                        }
                    }
                }
        }
        boolean isPalin(String s) {
            int i = 0, j = s.length() - 1;
            while(i < j) {
                if(s.charAt(i++) != s.charAt(j--)) {
                    return false;
                }
            }
            return true;
        }
        public String reverse(String t) {
            StringBuilder sb = new StringBuilder(t);
            return sb.reverse().toString();
        }
        Map<String,List<Integer>> initMap(String[] words) {
            Map<String,List<Integer>> map = new HashMap<>();
            for(int i = 0; i < words.length; i++) {
                List<Integer> ls = map.get(words[i]);
                if(ls == null) {
                    ls = new ArrayList<>();
                    map.put(words[i],ls);
                }
                ls.add(i);
            }
            return map;
        }
    }

Log in to reply
 

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