classSolution{public:intstrangePrinter(strings){constintn=s.length();vector<vector<int>>mem(n,vector<int>(n));returnstrangePrinter(s,0,n-1,mem);}private:// Returns the minimum number of turns to print s[i..j].intstrangePrinter(conststring&s,inti,intj,vector<vector<int>>&mem){if(i>j)return0;if(mem[i][j]>0)returnmem[i][j];// Print s[i].mem[i][j]=strangePrinter(s,i+1,j,mem)+1;for(intk=i+1;k<=j;++k)if(s[k]==s[i])mem[i][j]=min(mem[i][j],strangePrinter(s,i,k-1,mem)+strangePrinter(s,k+1,j,mem));returnmem[i][j];}};
1 2 3 4 5 6 7 8 910111213141516171819202122232425
classSolution{publicintstrangePrinter(Strings){finalintn=s.length();int[][]mem=newint[n][n];returnstrangePrinter(s,0,n-1,mem);}// Recursive helper method for strangePrinterprivateintstrangePrinter(Strings,inti,intj,int[][]mem){if(i>j)return0;if(mem[i][j]>0)returnmem[i][j];// Print s[i].mem[i][j]=strangePrinter(s,i+1,j,mem)+1;for(intk=i+1;k<=j;k++)if(s.charAt(k)==s.charAt(i))mem[i][j]=Math.min(mem[i][j],strangePrinter(s,i,k-1,mem)+//strangePrinter(s,k+1,j,mem));returnmem[i][j];}}
classSolution{public:intstrangePrinter(strings){if(s.empty())return0;constintn=s.size();// dp[i][j] := the minimum number of turns to print s[i..j]vector<vector<int>>dp(n,vector<int>(n,n));for(inti=0;i<n;++i)dp[i][i]=1;for(intj=0;j<n;++j)for(inti=j;i>=0;--i)for(intk=i;k<j;++k)dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]-(s[k]==s[j]));returndp[0][n-1];}};
1 2 3 4 5 6 7 8 910111213141516171819202122
classSolution{publicintstrangePrinter(Strings){if(s.isEmpty())return0;finalintn=s.length();// dp[i][j] := the minimum number of turns to print s[i..j]int[][]dp=newint[n][n];Arrays.stream(dp).forEach(A->Arrays.fill(A,n));for(inti=0;i<n;++i)dp[i][i]=1;for(intj=0;j<n;++j)for(inti=j;i>=0;--i)for(intk=i;k<j;++k)dp[i][j]=Math.min(dp[i][j],dp[i][k]+dp[k+1][j]-(s.charAt(k)==s.charAt(j)?1:0));returndp[0][n-1];}}
Thanks for stopping by! If you find this site helpful, consider buying me some protein powder to keep me fueled! 😄