企业官网建设流程全解析

链接：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(); vector<vector<int>> dp(m+1, vector<int>(n+1, 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); } };