暴力判断
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| class Solution {
public:
string findLongestWord(string s, vector<string>& dictionary) {
int n = s.size();
int maxLength{ 0 }, ret = -1;
for(int i = 0, sz = dictionary.size(); i < sz; ++i)
{
int j{ 0 };
int m = dictionary[i].size();
for(int q = 0; q < n && j < m; ++q)
{
if(s[q] == dictionary[i][j])
++j;
}
if(j == m)
{
if(m > maxLength)
{
ret = i;
maxLength = m;
}
if(m == maxLength && (ret == -1 || dictionary[i] < dictionary[ret]))
ret = i;
}
}
return ret == -1 ? "" : dictionary[ret];
}
};
|
先排序后在老方法判断也行，但是没有意义
dp(离谱)
f[i][j]表示第i位置之后j+'a'字母第一次出现的位置。
如果s[i] == j = 'a'，那么f[i][j] = i，否则f[i][j] = f[i + 1][j]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| class Solution {
public:
string findLongestWord(string s, vector<string>& dictionary) {
int n = s.size();
vector<vector<int>> dp(n + 1, vector<int>(26, n));
int ret = -1;
for(int i = n - 1; i >= 0; --i)
for(int j = 0; j < 26; ++j)
dp[i][j] = (s[i] == j + 'a') ? i : dp[i + 1][j];
for(int i = 0, sz = dictionary.size(); i < sz; ++i)
{
int m = dictionary[i].size(), j = 0;
int k = 0;
for(; j < m; ++j)
{
if(dp[k][dictionary[i][j] - 'a'] == n)
break;
else
k = dp[k][dictionary[i][j] - 'a'] + 1;
}
if(j == m)
if(ret == -1 || (m > dictionary[ret].size() || (m == dictionary[ret].size() && dictionary[i] < dictionary[ret])))
ret = i;
}
return ret == -1 ? "" : dictionary[ret];
}
};
|