Concise Java Solution


  • 17
    J
    public class Solution {
        public List<List<String>> partition(String s) {
            List<List<String>> res=new ArrayList<List<String>>();
            if(s.length()==0)return res;
            recur(res,new ArrayList<String>(),s);
            return res;
        }
        
        public void recur(List<List<String>> res,List<String> temp, String s){
            if(s.length()==0){
                res.add(new ArrayList<String>(temp));
                return;
            }
            for(int i=0;i<s.length();i++){
                if(isPalin(s.substring(0,i+1))){
                    temp.add(s.substring(0,i+1));
                    recur(res,temp,s.substring(i+1));
                    temp.remove(temp.size()-1);
                }
            }
        }
        
        public boolean isPalin(String s){
            for(int i=0;i<s.length()/2;i++){
                if(s.charAt(i)!=s.charAt(s.length()-1-i))return false;
            }
            return true;
        }
    }

  • 0
    S

    Similar idea.

    In order to check whether a string is palindrome, simply compare to reversed itself.

    public class Solution {
        public List<List<String>> partition(String s) {
            List<List<String>> res = new ArrayList<List<String>>();
            partition(res, new ArrayList<String>(), s);
            return res;
        }
        
        public void partition(List<List<String>> res, List<String> list, String s) {
            if(isPali(s)) {
                List<String> l = new ArrayList<String>(list);
                l.add(s);
                res.add(l);
            }
                
            for(int i = 1; i < s.length(); i++) {
                String s1 = s.substring(0, i), s2 = s.substring(i, s.length());
                if(isPali(s1)) {
                    List<String> ll = new ArrayList<String>(list);
                    ll.add(s1);
                    partition(res, ll, s2);
                }
            }
        }
        
        public boolean isPali(String s) {
            return s.equals(new StringBuilder(s).reverse().toString());
        }
    }

  • 0
    F

    What's the time complexity of this method? In the recur(), there is a for loop, which is O(n); isPalin() is another O(n); substring() is another O(n); and recur() is another O(n). So can I say that it's O(n^4) in the worst case?


  • 0

    @SpicyDog More concise, but using sb to check for palindrome is slower.


  • 0
    N

    said in Concise Java Solution:

        return res;
    

    @jie17 can you please let me know the time complexity of the code


  • 0
    Y

    @nikhilay I think the time complexity is O(n! * n * n) . Here n presents the length of the given string. n! is for the n-branch tree with n-level depth. The rest one n is for the palindrome check and another n is for the substring method.


Log in to reply
 

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