C++ Dp beat 97%


  • 0
    B

    Just a little improvement. short the string first.

    int strangePrinter(string s) {
        string str=shortstr(s);
        if(str.length()<2)return str.length();
        int n=str.length();
        vector<vector<int>> dp(n,vector<int>(n,1));
        for(int i=1;i<n;i++)
        {
            for(int j=0;i+j<n;j++)
            {
                char x=str[i+j];
                dp[j][j+i]=dp[j][j+i-1]+1;
                for(int k=j;k<i+j;k++)
                {
                    if(str[k]==x)
                    {
                        int temp=dp[k][i+j-1];
                        if(k>j)temp+=dp[j][k-1];
                        dp[j][j+i]=min(dp[j][i+j],temp);
                    }
                }
            }
        }
        return dp[0][n-1];
    }
    string shortstr(string &s)
    {
        string result="";
        int i=0;
        while(i<s.length())
        {
            char x=s[i];
            while(i<s.length() && s[i]==x)i++;
            result+=x;
        }
        return result;
    }

Log in to reply
 

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