Leetcode Word Break II
Word Break II
Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.
Return all such possible sentences.
For example, given s =
A solution is
難易度は5つ星です.
難易度指数はword ladder IIに迫った
主な難点:極致に最適化するには、再帰遡及法を直接使用することはできません.そうしないと、タイムアウトします.
本プログラムの方法:
1 2 Dテーブルvector>tblを使用して記録し、i点から次のbreak位置にジャンプできるかどうかを記録します.できない場合は、tbl[i]は空です.可能であれば、どの位置にジャンプできるかを記録します.
2次元テーブルを使用して再帰遡及法を最適化します.
最適化ポイント:
現在の位置がstartであるがtbl[start]が空である場合、このbreak位置はs列全体をbreakすることができず、次の層を検索する必要がなく、直接上の層に戻ることができない.
最適化の結果は次のとおりです.
次のようなビッグデータに遭遇した場合:
Input: "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab", ["a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa"]
Expected: []
出力結果が空であれば,本プログラム,実行時間を用い,動的計画法テーブルを構築するだけでO(n*n)時間複雑度(実際の実行はO(n))を用い,再帰遡及時にはO(1)を用いて結果を返すことができる.
これも本題の考査の重点です:多くのビッグデータの例は[]空の結果を返すことです.
もちろん、出題者がこのように私たちを試験しに来たことを知っていれば、私たちは直接このような状況を排除することができて、过ごすことができます.それでは難易度指数は3~4星級に下がります.
本プログラムは,このような状況に連打帯消地で対処した効率が非常に高く,12 msの稼働時間の戦果があった.
ネット上の多くのブログのプログラムよりも最適化するには、ダイナミックプランニングテーブルの構築力が鍵であり、本プログラムの構築方法が最適であるべきである.改善できる歓迎のご指導があります.
Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.
Return all such possible sentences.
For example, given s =
"catsanddog" , dict = ["cat", "cats", "and", "sand", "dog"] . A solution is
["cats and dog", "cat sand dog"] . 難易度は5つ星です.
難易度指数はword ladder IIに迫った
主な難点:極致に最適化するには、再帰遡及法を直接使用することはできません.そうしないと、タイムアウトします.
本プログラムの方法:
1 2 Dテーブルvector
2次元テーブルを使用して再帰遡及法を最適化します.
最適化ポイント:
現在の位置がstartであるがtbl[start]が空である場合、このbreak位置はs列全体をbreakすることができず、次の層を検索する必要がなく、直接上の層に戻ることができない.
最適化の結果は次のとおりです.
次のようなビッグデータに遭遇した場合:
Input: "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab", ["a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa"]
Expected: []
出力結果が空であれば,本プログラム,実行時間を用い,動的計画法テーブルを構築するだけでO(n*n)時間複雑度(実際の実行はO(n))を用い,再帰遡及時にはO(1)を用いて結果を返すことができる.
これも本題の考査の重点です:多くのビッグデータの例は[]空の結果を返すことです.
もちろん、出題者がこのように私たちを試験しに来たことを知っていれば、私たちは直接このような状況を排除することができて、过ごすことができます.それでは難易度指数は3~4星級に下がります.
本プログラムは,このような状況に連打帯消地で対処した効率が非常に高く,12 msの稼働時間の戦果があった.
ネット上の多くのブログのプログラムよりも最適化するには、ダイナミックプランニングテーブルの構築力が鍵であり、本プログラムの構築方法が最適であるべきである.改善できる歓迎のご指導があります.
class Solution {
public:
//2014-2-19 update
vector<string> wordBreak(string s, unordered_set<string> &dict)
{
vector<string> rs;
string tmp;
vector<vector<int> > tbl = genTable(s, dict);
word(rs, tmp, s, tbl, dict);
return rs;
}
void word(vector<string> &rs, string &tmp, string &s, vector<vector<int> > &tbl,
unordered_set<string> &dict, int start=0)
{
if (start == s.length())
{
rs.push_back(tmp);
return;
}
for (int i = 0; i < tbl[start].size(); i++)
{
string t = s.substr(start, tbl[start][i]-start+1);
if (!tmp.empty()) tmp.push_back(' ');
tmp.append(t);
word(rs, tmp, s, tbl, dict, tbl[start][i]+1);
while (!tmp.empty() && tmp.back() != ' ') tmp.pop_back();//tmp.empty()
if (!tmp.empty()) tmp.pop_back();
}
}
vector<vector<int> > genTable(string &s, unordered_set<string> &dict)
{
int n = s.length();
vector<vector<int> > tbl(n);
for (int i = n - 1; i >= 0; i--)
{
if(dict.count(s.substr(i))) tbl[i].push_back(n-1);
}
for (int i = n - 2; i >= 0; i--)
{
if (!tbl[i+1].empty())//if we can break i->n
{
for (int j = i, d = 1; j >= 0 ; j--, d++)
{
if (dict.count(s.substr(j, d))) tbl[j].push_back(i);
}
}
}
return tbl;
}
};