DP:segment string
1352 ワード
Segment a long string into a set of valid words using a dictionary. Return the maximum number of the subwords.
この問題はフェイスブックの面接問題から出た.
方法1:マトリクス連積モデルをセットする.複雑度O(N^3)
最長上昇サブシーケンスを適用:複雑度O(N^2)
この問題はフェイスブックの面接問題から出た.
方法1:マトリクス連積モデルをセットする.複雑度O(N^3)
int segmentString(string str, set dict)
{ // O(N^3)
int len = str.length();
vector > f(len, vector(len, 0));
for (int k = 0; k < len; ++k)
{
for (int i = 0; i < (len - k); ++i)
{
int j = i + k;
if (dict.find(str.substr(i, k + 1)) != dict.end())
{
f[i][j] = 1;
}
for (int t = i; t < j; ++t)
{
if (f[i][t] && f[t+1][j])
{
f[i][j] = max(f[i][j], f[i][t] + f[t+1][j]);
}
}
}
}
return f[0][len-1];
}
最長上昇サブシーケンスを適用:複雑度O(N^2)
int segmentString2(string str, set dict)
{
int len = str.length();
vector f(len, 0);
for (int i = 0; i < len; ++i)
{
for (int j = i-1; j >= 0; --j)
{
if (dict.find(str.substr(j + 1, i)) != dict.end() &&
f[j])
{
f[i] = max(f[i], f[j] + 1);
}
}
}
return f[len - 1];
}