断字问题
在输入此问题时，给出的一个句子不带空格，还提供了另一本词典，其中包含一些有效的英语单词。我们必须找到在单个词典单词中打断句子的可能方法。
当找到有效单词时，我们将尝试从字符串的左侧搜索以找到有效单词，我们将在该字符串的下一部分中搜索单词。
输入输出
Input:
A set of valid words as dictionary, and a string where different words are placed without spaces.
Dictionary: {mobile, sam, sung, man, mango, icecream, and, go, i, love, ice, cream}
Given String: “ilovemangoicecream”
Output:
All possible ways to break the string into given words.
i love man go ice cream
i love man go icecream
i love mango ice cream
i love mango icecream算法
wordBreak(string, n, result)
输入-给定的字符串，字符串的长度，分隔的字符串。
输出-使用字典分隔字符串。
Begin
for i := 0 to n, do
subStr := substring of given string from (0..i)
if subStr is in dictionary, then
if i = n, then
result := result + subStr
display the result
return
wordBreak(substring from (i..n-i), n-i, result, subStr, ‘space’)
done
End示例
#include <iostream>
#define N 13
using namespace std;
string dictionary[N] = {"mobile","samsung","sam","sung","man","mango", "icecream","and",
"go","i","love","ice","cream"};
int isInDict(string word){ //check whether the word is in dictionary or not
for (int i = 0; i < N; i++)
if (dictionary[i].compare(word) == 0)
return true;
return false;
}
void wordBreak(string str, int n, string result) {
for (int i=1; i<=n; i++) {
string subStr = str.substr(0, i); //get string from 0 to ith location of the string
if (isInDict(subStr)) { //if subStr is found in the dictionary
if (i == n) {
result += subStr; //add substring in the result.
cout << result << endl;
return;
}
wordBreak(str.substr(i, n-i), n-i, result + subStr + " "); //otherwise break rest part
}
}
}
int main() {
string str="iloveicecreamandmango";
wordBreak(str, str.size(),"");
}输出结果
i love man go ice cream i love man go icecream i love mango ice cream i love mango icecream