Recursion solution in JAVA get LTE


  • 0
    T
    public class Solution {
    public List<List<String>> L= new LinkedList<List<String>>();
    public String S;
    public List<List<String>> partition(String s) {
        if(s.length()==0) return L;
        S=s;
        String tmps=S.substring(0,1);
        findP(new LinkedList<String>(), tmps, 1);
        return L;
    }
    
    void findP(List<String> l, String tmps, int x){
        if(x>S.length()) return;
        if(isPalindrome(tmps)){
            List<String> tmpl = new LinkedList<String>(l);
            //can be put into the list
            tmpl.add(tmps);
            if(x==S.length()){ //add to the list
                L.add(tmpl);
                return;
            }
            String tmp = S.substring(x,x+1);
            findP(tmpl,tmp,x+1);
        }
        
        if(x<S.length()){
            tmps.concat(S.substring(x,x+1));
            findP(l,tmps,x+1);
        }
        
    }
    
    boolean isPalindrome(String tmps){
        if(tmps.length()==0) return false;
        if(tmps.length()==1) return true;
        int i=0;
        int j=tmps.length()-1;
        while(i<=j){
            if(tmps.charAt(i)!=tmps.charAt(j)) return false;
            i++;
            j--;
        }
        return true;
    }
    

    }

    It seems that every thing is necessary to get the answer. Is the only way I can improve is to use DP?


Log in to reply
 

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