分词问题
什么是分词问题？
分词问题是计算机科学中的一个逻辑难题，要求我们检查给定的字符串是否可以从字典中分割成一系列单词。例如，如果给定的字符串是"ramhaspenandapple"，而字典是["ram", "and", "has", "apple", "pen"]，则答案为真，因为该字符串可以分割为"ram has pen and apple"。
使用回溯法解决分词问题
在本问题的输入中，给出了一个不带空格的句子，另一个字典中也提供了一些有效的英语单词。我们必须找到将句子拆分成单个字典单词的可能方法。给定的字符串和字典如下 −
字典：{ram, samuel, winter, man, mango, icecream, and, i, love, ice, cream}
给定字符串："ilovewinterandicecream"
我们将尝试从字符串的左侧搜索以找到有效的单词。当找到有效的单词时，我们将在该字符串的下一部分中搜索单词。将字符串拆分成给定单词的所有可能方法都是 −
i love winter and ice cream i love winter and icecream
解决这个问题的一种方法是使用回溯法。这是一种尝试不同组合，如果部分解决方案无效则回溯的技术。其基本思想是从字符串的开头开始，检查前缀是否是指定字典中的单词。如果是，则递归检查剩余的后缀是否可以切分为单词。如果前缀和后缀都有效，则返回 true 并将其标记为解决方案的一部分。否则，回溯并尝试不同的前缀。
伪代码
以下是使用回溯方法解决断词问题的伪代码 −
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 <stdio.h>
#include <string.h>
#define N 13
char *dictionary[N] = {"mobile","samsung","sam","sung","man","mango", "icecream","and", "go","i","love","ice","cream"};
//检查该单词是否在字典中
int isInDict(char *word){
for (int i = 0; i < N; i++)
if (strcmp(dictionary[i], word) == 0)
return 1;
return 0;
}
void wordBreak(char *str, int n, char *result) {
for (int i=1; i<=n; i++) {
//获取从 0 到第 i 个位置的字符串
char subStr[100];
strncpy(subStr, str, i);
subStr[i] = '\0';
//如果在字典中找到 subStr
if (isInDict(subStr)) {
if (i == n) {
//在结果中添加子字符串
strcat(result, subStr);
printf("%s
", result);
return;
}
//否则中断其余部分
char newResult[100];
strcpy(newResult, result);
strcat(newResult, subStr);
strcat(newResult, " ");
wordBreak(str + i, n-i, newResult);
}
}
}
int main() {
char str[] = "iloveicecreamandmango";
char result[100] = "";
wordBreak(str, strlen(str), result);
return 0;
}
#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){
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++) {
//获取从 0 到第 i 个位置的字符串
string subStr = str.substr(0, i);
//如果在字典中找到 subStr
if (isInDict(subStr)) {
if (i == n) {
//在结果中添加子字符串
result += subStr;
cout << result << endl;
return;
}
//否则打破其余部分
wordBreak(str.substr(i, n-i), n-i, result + subStr + " ");
}
}
}
int main() {
string str="iloveicecreamandmango";
wordBreak(str, str.size(),"");
}
import java.util.Arrays;
import java.util.List;
public class Main {
static final List<String> DICTIONARY = Arrays.asList("mobile","samsung","sam","sung","man","mango", "icecream","and", "go","i","love","ice","cream");
//检查该词是否在字典中
public static boolean isInDict(String word){
return DICTIONARY.contains(word);
}
public static void wordBreak(String str, int n, String result) {
for (int i=1; i<=n; i++) {
//获取从 0 到第 i 个位置的字符串
String subStr = str.substring(0, i);
//如果在字典中找到 subStr
if (isInDict(subStr)) {
if (i == n) {
//在结果中添加子字符串
result += subStr;
System.out.println(result);
return;
}
//否则打破其余部分
wordBreak(str.substring(i, n), n-i, result + subStr + " ");
}
}
}
public static void main(String[] args) {
String str = "iloveicecreamandmango";
wordBreak(str, str.length(), "");
}
}
# 定义字典
dictionary = ["mobile","samsung","sam","sung","man","mango","icecream","and","go","i","love","ice","cream"]
# 检查单词是否在字典中
def isInDict(word):
return word in dictionary
# 拆分单词的函数
def wordBreak(str, n, result):
for i in range(1, n+1):
# 获取从 0 到第 i 个位置的字符串
subStr = str[:i]
# 如果在字典中找到 subStr
if isInDict(subStr):
if i == n:
# 在结果中添加子字符串
result += subStr
print(result)
return
# 否则中断其余部分
wordBreak(str[i:], n-i, result + subStr + " ")
# Main function
def main():
str = "iloveicecreamandmango"
wordBreak(str, len(str), "")
# Call the main function
if __name__ == "__main__":
main()
输出
i love ice cream and man go i love ice cream and mango i love icecream and man go i love icecream and mango
