Having some trouble partitioning the string into palindromes


  • 1
    S

    So my code is found down below and I kind of use the same code from longest palindrome, but:

    1.       my output is : [["c","d","d"], ["dd"]]  
      
    2. expected output is : [["c","d","d"],["c","dd"]]

    I thought the first array list was palindromes with a single center and the second one was with a double center (like abba). But i later realized that I had to create different possibilities for the partition of the string, should I start from the beginning or can I use the same approach? I think my current time complexity is O(n).

      public class Solution {
        public ArrayList<ArrayList<String>> partition(String s) {
            ArrayList<ArrayList<String>> mehh= new ArrayList<ArrayList<String>>();
            int n=s.length();
            if(n==0) return mehh;
            ArrayList<String>x1=new ArrayList<String>();
            ArrayList<String>x2=new ArrayList<String>();
            if(n==1) {
                x1.add(s);
                mehh.add(x1);
                return mehh;
            }
            
    
            for(int i=0; i< n ;i++){
                String p1=expandAroundCenter(s,i,i);
                if(!p1.equals("")) x1.add(p1);
                String p2=expandAroundCenter(s,i,i+1);
                if(!p2.equals("")) x2.add(p2);
            }
            if(x1.size()!=0) mehh.add(x1);
            if(x2.size()!=0) mehh.add(x2);
           // mehh.add(x1);
            return mehh;
        }
        
        public String expandAroundCenter(String s, int c1,int c2){
            int l=c1,r=c2;
            int n=s.length();
            while(l>=0 && r<=n-1 && s.charAt(l)==s.charAt(r)){
                l--;
                r++;
            }
            return s.substring(l+1,r);
        }
    }

Log in to reply
 

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