JAVA DP recursive 5ms solution


  • 4
    public class Solution {
    int[] cut;
    public int minCut(String s) {
        int len=s.length();
        char[] tmp=s.toCharArray();
        cut=new int[s.length()];
        Arrays.fill(cut,Integer.MAX_VALUE);
        for(int i=0;i<len;i++)
        {
            re(tmp,i,i);
            re(tmp,i-1,i);
        }
        return cut[len-1];
    }
        public void re(char[] s,int start,int end)
        {
            if(start<0||end>=s.length)return;
            if(s[start]==s[end])
            {
                re(s,start-1,end+1);
                int tmp=start==0?0:cut[start-1]+1;
    		    cut[end]=Math.min(tmp,cut[end]);
            }
        }
    }

  • 0
    M

    @tjcd Could you explain it a little?


  • 0

    @mishrasonu1993 if you write a top-down algorithm, you can see the relationship between two iterations is

    dp[i][j] = (c[i]==c[j]&&dp[i+1][j-1])
    

    we only use the previous result which is inside the current string. we can do it by storing all data in 2-d array but we can also do it in a bottom-up way that is "from inside to outside". The benefit is that we can save that 2-d space and make algorithm faster. But I think top-down algorithm is ok when you are doing an interview I guess :).


Log in to reply
 

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