Skip to content
Branch: master
Find file History
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
..
Failed to load latest commit information.
README.md
solve.cpp

README.md

Word Break

Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

For example, given s = "leetcode", dict = ["leet", "code"].

Return true because "leetcode" can be segmented as "leet code".

Solution

类似DP思想:

使用dp[i]表示前面i个字符(0 ~ i - 1)是否可以break, 显然dp[i]取决于i之前是否可以break,并且dp[0] = true,即

for j from 0 to 1
	if dp[j] && s[i:j] in dict
		dp[i] = true
		break

于是实现代码为:

bool wordBreak(string s, const unordered_set<string> &dict) {
	int n = s.size();
	vector<bool> canBreak(n + 1, false);
	canBreak[0] = true;
	for (int i = 1; i <= n; ++i) {
		for (int j = 0; j < i; ++j) {
			if (canBreak[j] && dict.find(s.substr(j, i - j)) != dict.end()) {
				canBreak[i] = true;
				break;
			}
		}
	}
	return canBreak[n];
}

扩展

Word Break II: 打印所有的结果

You can’t perform that action at this time.