显然我们得按顺序获得目标t的每个字符。对于我们可以在s中找到这么一个子序列。显然如果找到尾巴还是没有需要的
。就得从s[0]开始重新开始顺序找。(然后答案递增,因为表示要重新开始加一个子序列了) 所以不能直接找。所以我们可以另外开一个数组
表示在i-1位置,如果要找下一个紧接着的j的话,需要到哪个位置找。
复杂度O(26*n)
int nxt[26][100010]; class Solution { public: /** * * @param s string字符串 * @param t string字符串 * @return int整型 */ int string(string s, string t) { int n = s.size(); int m = t.size(); for(int i = 0; i < 26; i ++) for(int j = 0; j <= n; j ++) nxt[i][j] = n; for(int i = 0; i < 26; i ++) for(int j = n - 1; j >= 0; j --) nxt[i][j] = (s[j] == 'a' + i ? j : nxt[i][j + 1]); int cur = 0; int ans = 1; for(int i = 0; i < m; i ++) { int x = t[i] - 'a'; if(nxt[x][0] == n) return -1; if(nxt[x][cur] == n) {ans ++; cur = 0;} cur = nxt[x][cur] + 1; } return ans; } };