why my solution is so slow? thanks


  • 0

    this solution is Accepted, but it's very slow, just on the edge of "Time limit exceeded".
    How to improve it? any help would be appreciated.

    public class Solution {
        public List<List<Integer>> palindromePairs(String[] words) {
            List<List<Integer>> result = new ArrayList<List<Integer>>();
            if (words.length == 0) {
                return result;
            }
            HashMap<String, Integer> set = new HashMap<String, Integer>();
            for(int i = 0; i < words.length; i++){
                set.put(words[i], i);
            }
            for (int k = 0; k < words.length; k++) {
                String rev = new StringBuffer(words[k]).reverse().toString();
                for(int i = 0; i <= rev.length(); i++){
                    String substr = rev.substring(0, i);
                    String substrRest = rev.substring(i);
    
                    if(set.containsKey(substr)
                    && isPalindrome(substrRest)
                    && set.get(substr) != k ){
                        addResult(result, set.get(substr), k);
                    }
                    
                    if( set.containsKey(substrRest)
                    && isPalindrome(substr)
                    && set.get(substrRest) != k) {
                        addResult(result, k, set.get(substrRest));
                    }
                }
            }
            return result;
        }
        private void addResult(List<List<Integer>> result, int idx1, int idx2){
            ArrayList<Integer> l = new ArrayList<Integer>(Arrays.asList(idx1, idx2));
            if(!result.contains(l)){
                result.add(l);
            }
        }
        private boolean isPalindrome(String str){
            return new StringBuffer(str).reverse().toString().equals(str);
        }
    }
    

Log in to reply
 

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