LeetCode 140. Word Break II (DP+DFS)
TLE(Time Limit Exceeded)を直接再帰的に解き、
wordBreakの解MLE(Memory Limit Exceeded)をvectorret(s.size()+1)で保存し、
DP+DFSでテストに合格した.
LeetCode 139.Word Breakでは、s.substr(0,i)がdictの文字列から構成できるかどうかをdp[i]で識別する.
ここでは,s.substr(0,i)のworkBreak解の最後の単語の集合をdp[i]で識別する.
「"abcdefg",{"a","bc","abc","ab","c"}」と入力すると
ではdp[3]=["bc","abc","c"].
dp[now]に基づいてこの集合を得ることができます
集合中の特定の要素strを考察すると,now−str.size()によりstrの順継文字列を推定し,dfs解を行うことができる.
コード:
wordBreakの解MLE(Memory Limit Exceeded)をvector
DP+DFSでテストに合格した.
LeetCode 139.Word Breakでは、s.substr(0,i)がdictの文字列から構成できるかどうかをdp[i]で識別する.
ここでは,s.substr(0,i)のworkBreak解の最後の単語の集合をdp[i]で識別する.
「"abcdefg",{"a","bc","abc","ab","c"}」と入力すると
ではdp[3]=["bc","abc","c"].
dp[now]に基づいてこの集合を得ることができます
集合中の特定の要素strを考察すると,now−str.size()によりstrの順継文字列を推定し,dfs解を行うことができる.
コード:
class Solution
{
public:
vector<string> wordBreak(string s, unordered_set<string> &dict)
{
vector<vector<string>> dp(s.size()+1);
dp[0].push_back(string(""));
for (size_t i = 0; i < s.size(); ++ i)
{
if (dp[0].empty() == true)
{
continue;
}
for (size_t length = 1; i + length <= s.size(); ++ length)
{
if (dict.find(s.substr(i, length)) == dict.end())
{
continue;
}
dp[i + length].push_back(s.substr(i, length));
}
}
dfs(string(), dp, s.size());
return ret;
}
private:
void dfs(string str, vector<vector<string>>& dp, size_t now)
{
if (now == 0)
{
ret.push_back(str);
return ;
}
for (auto it = dp[now].begin(); it != dp[now].end(); ++ it)
{
string new_str = (str.empty()? *it: *it + " " + str);
dfs(new_str, dp, now - it->size());
}
}
vector<string> ret;
};