单词拆分问题

什么是单词拆分问题？

单词拆分问题是计算机科学中的一道逻辑谜题，要求我们检查给定的字符串是否可以分割成字典中的一系列单词。例如，如果给定的字符串是“ramhaspenandapple”，字典是["ram", "and", "has", "apple", "pen"]，则答案为真，因为该字符串可以分割成“ram has pen and apple”。

使用回溯法解决单词拆分问题

在本问题的输入中，给出一个没有空格的句子，另一个字典也提供了一些有效的英文单词。我们必须找到将句子分解成单个字典单词的所有可能方法。给定的字符串和字典如下：

Dictionary: {ram, samuel, winter, man, mango, icecream, and, i, love, ice, cream}
Given String: "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

示例

在下面的示例中，我们将实际演示如何解决单词拆分问题。

C C++ Java Python

#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"};
//check whether the word is in dictionary or not
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++) {
      //get string from 0 to ith location of the string 
      char subStr[100];
      strncpy(subStr, str, i);
      subStr[i] = '\0';

      //if subStr is found in the dictionary
      if (isInDict(subStr)) {       
         if (i == n) {
            //add substring in the result
            strcat(result, subStr); 
            printf("%s\n", result);
            return;
         }
         //otherwise break rest part
         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"};
//check whether the word is in dictionary or not
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++) {
      //get string from 0 to ith location of the string 
      string subStr = str.substr(0, i);       
      //if subStr is found in the dictionary
      if (isInDict(subStr)) {       
         if (i == n) {
            //add substring in the result
            result += subStr; 
            cout << result << endl;
            return;
         }
         //otherwise break rest part
         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");
   //check whether the word is in dictionary or not
   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++) {
         //get string from 0 to ith location of the string 
         String subStr = str.substring(0, i);
         //if subStr is found in the dictionary
         if (isInDict(subStr)) {
            if (i == n) {
               //add substring in the result
               result += subStr;
               System.out.println(result);
               return;
            }
            //otherwise break rest part
            wordBreak(str.substring(i, n), n-i, result + subStr + " ");
         }
      }
   }
   public static void main(String[] args) {
      String str = "iloveicecreamandmango";
      wordBreak(str, str.length(), "");
   }
}

# Define the dictionary
dictionary = ["mobile","samsung","sam","sung","man","mango", "icecream","and", "go","i","love","ice","cream"]

# Check whether the word is in dictionary or not
def isInDict(word):    
   return word in dictionary

# Function to break the word
def wordBreak(str, n, result):
   for i in range(1, n+1):
      # Get string from 0 to ith location of the string 
      subStr = str[:i]

      # If subStr is found in the dictionary
      if isInDict(subStr):       
         if i == n:
            # Add substring in the result
            result += subStr
            print(result)
            return

         # Otherwise break rest part
         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

打印页面