單詞拆分問題

什麼是單詞拆分問題？

單詞拆分問題是計算機科學中的一道邏輯謎題，要求我們檢查給定的字串是否可以分割成字典中的一系列單詞。例如，如果給定的字串是“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

列印頁面