This link has two nice solutions, one updating from forth to back (posted by tqlong in the post) and the other updating from back to forth (posted by diego2 in the answer). The reversed updating one, if written in C++ as follows, achieves 12ms, 4ms faster than that of tqlong.
1 class Solution { 2 public: 3 int minCut(string s) { 4 int n = s.length(); 5 vector<int> cut(n + 1); 6 iota(cut.rbegin(), cut.rend(), -1); 7 for (int i = n - 1; i >= 0; i--) { 8 for (int l = i, r = i; l >= 0 && r < n && s[l] == s[r]; l--, r++) 9 cut[l] = min(cut[l], cut[r + 1] + 1); 10 for (int l = i, r = i + 1; l >= 0 && r < n && s[l] == s[r]; l--, r++) 11 cut[l] = min(cut[l], cut[r + 1] + 1); 12 } 13 return cut[0]; 14 } 15 };
Well, someone even achieves 4ms running time in C++, which makes me feel like to give a try. I use int* instead of vector<int> and change string s to const char* ss using s.c_str(). Now the code takes only 4ms, though looks not so nice :-)
1 class Solution { 2 public: 3 int minCut(string s) { 4 int n = s.length(), *cut = new int[n + 1]; 5 for (int i = 0; i < n; i++) cut[i] = i - 1; 6 cut[n] = -1; 7 const char *ss = s.c_str(); 8 for (int i = n - 1; i >= 0; i--) { 9 for (int l = i, r = i; l >= 0 && r < n && ss[l] == ss[r]; l--, r++) 10 cut[l] = min(cut[l], cut[r + 1] + 1); 11 for (int l = i, r = i + 1; l >= 0 && r < n && ss[l] == ss[r]; l--, r++) 12 cut[l] = min(cut[l], cut[r + 1] + 1); 13 } 14 return cut[0]; 15 } 16 };
