My accepted Java solution. Using Map.


  • 1
    Z
    public class Solution {
        public List<List<Integer>> palindromePairs(String[] words) {
            Set<List<Integer>> res = new HashSet<List<Integer>>();
            HashMap<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++) {
                String s = words[i];
                for(int k=0;k<=s.length();k++) {
                    String prefix = s.substring(0,k);
                    String suffix = s.substring(k);
                    if(isPal(prefix) && map.containsKey(reverse(suffix)) &&
                        map.get(reverse(suffix)) != i) {
                        ArrayList<Integer> tmp = new ArrayList<Integer>();
                        tmp.add(map.get(reverse(suffix)));
                        tmp.add(i);
                        res.add(tmp);        
                    }
                }
                s = reverse(words[i]);
                for(int k=0;k<=s.length();k++) {
                    String prefix = s.substring(0,k);
                    String suffix = s.substring(k);
                    if(isPal(prefix) && map.containsKey(suffix) &&
                        map.get(suffix) != i) {
                        ArrayList<Integer> tmp = new ArrayList<Integer>();
                        tmp.add(i);
                        tmp.add(map.get(suffix));
                        res.add(tmp);        
                    }
                }
                
            }
            List<List<Integer>> retVal =new ArrayList<List<Integer>>();
            for(List<Integer> l:res) {
                retVal.add(l);
            }
            return retVal;
        }
        public String reverse(String s) {
            return new StringBuilder(s).reverse().toString();
        }
        public boolean isPal(String s){
            for(int i=0,j=s.length()-1;i<j;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.