857 · 最小的窗口子序列(双序列dp)

链接LintCode 炼码 - 更高效的学习体验题解dp[i][j] 长度为i的s匹配长度为j的t子序列的开始长度的[0,i]中间的数值判断dp[i][t.size()]是有成功的子序列长度是i-dp[i][t.size()]1,打擂台class Solution { public: /** * param s: a string * param t: a string * return: the minimum substring of S */ string minWindow(string s, string t) { // Write your code here int m s.size(); int n t.size(); vectorvectorint dp(m1, vectorint(n1, 0)); for (int i 1; i m; i) { for (int j 1; j n; j) { if (s[i-1] ! t[j-1]) { dp[i][j] dp[i-1][j]; } else { if (j 1) { dp[i][j] i-1; } else { dp[i][j] dp[i-1][j-1]; } } } } int start 0; int len INT_MAX; // abcd 4 // abd for (int i 1; i m; i) { if (dp[i][n] ! 0) { int tmp_len i - dp[i][n]; int tmp_start dp[i][n]; if (tmp_len len) { len tmp_len; start tmp_start; } } } if (len INT_MAX) { return ; } return s.substr(start, len); } };