Word Break Problem in Java

2025年5月3日 | 阅读 9 分钟

单词拆分问题 (Word Break Problem) 是指判断一个给定的字符串是否可以被拆分成若干个有效的单词，而这些单词都存在于一个给定的字典中。目标是确定该字符串是否可以从字典中的单词列表里分割成一个或多个单词。这个问题可以通过多种方法来解决，包括递归、回溯或动态规划。解决方案涉及检查有效的词首，并递归地检查字符串的剩余部分是否也能被分割成字典中的单词。

字典

{ i, like, sam, sung, samsung, mobile, ice, cream, icecream, man, go, mango }

示例 1

输入: ilikeicecream

输出： 是

该字符串可以被分割为 “i like ice cream” 或 “i likeicecream”。

示例 2

输入: mangoicecream

输出： 是

该字符串可以被分割为 “mango ice cream” 或 “mangoicecream”。

示例 3

输入: samsungmobile

输出： 是

该字符串可以被分割为 “samsung mobile”。

使用递归方法

单词拆分问题的递归方法涉及将目标字符串拆分成词首，并检查每个词首是否存在于字典中。如果找到一个词首，函数会递归地检查剩余的子字符串，并持续这个过程，直到整个字符串都被分割，或者所有可能性都已用尽，从而导致成功或失败。

算法

步骤 1: 以字典（单词列表）和目标（要分割的字符串）作为输入。

步骤 2: 如果目标字符串为空，则返回 true（空字符串被视为已分割）。

步骤 3: 对于从 1 到目标字符串长度的每个索引 i，提取词首子字符串。

步骤 4: 如果词首在字典中，则递归地检查剩余字符串是否可以被分割。

步骤 5: 如果任何递归调用导致成功分割，则返回 true；否则，返回 false。

让我们在 Java 程序中实现上述方法。

文件名: WordSegmenter.java

import java.util.*;  
public class WordSegmenter {  // Defining the class WordSegmenter
    // Method to check if the target string can be segmented into words from the dictionary
    static boolean isSegmentable(List<String> dictionary, String target) {
        // Base case: if the target string is empty, it can be segmented
        if (target.isEmpty()) {
            return true;  // Return true for an empty string as it is considered segmented
        }
        // Calculate the length of the target string
        int targetLength = target.length();
        // Loop through the target string, checking prefixes from index 1 to the target length
        for (int i = 1; i <= targetLength; ++i) {
            // Extract the prefix substring from the target string
            String prefix = target.substring(0, i);
            // Check if the prefix is in the dictionary
            // If true, recursively check if the remaining part of the string can be segmented
            if (dictionary.contains(prefix) && isSegmentable(dictionary, target.substring(i))) {
                return true;  // If a valid segmentation is found, return true
            }
        }
        // If no valid segmentation is found, return false
        return false;
    }
    // Main method: Entry point of the program
    public static void main(String[] args) {
        // Create a list of dictionary words
        List<String> dictionary = Arrays.asList(
            "apple", "pen", "pine", "pineapple", "cat", 
            "cats", "dog", "sand", "and", "catdog");
        // Check if the string "pineapplepenapple" can be segmented using the dictionary
        boolean result = isSegmentable(dictionary, "pineapplepenapple");
        // Print the result (true if the string can be segmented, false otherwise)
        System.out.println(result);  // Output: true
    }
}   

输出

 
true

时间复杂度: O(2^N)， 因为每个词首都会产生指数级的递归调用。

辅助空间: O(N)， 用于递归栈深度，最多为目标字符串的长度。

使用动态规划

单词拆分问题的动态规划方法涉及创建一个布尔数组来存储子字符串是否可以被分割成有效的字典单词。通过遍历字符串并利用先前计算的结果，该方法优化了分割检查，并有效地确定整个字符串是否可以由字典中的单词组成。

算法

步骤 1: 如果输入字符串为空，则返回 true，因为它始终可以被分割。

步骤 2: 初始化一个大小为 inputString.length() + 1 的布尔数组 dpTable，用于存储子问题的结果。

步骤 3: dpTable[i] 为 true，表示子字符串 inputString[0..i-1] 可以被分割成字典中的单词。

步骤 4: 遍历输入字符串的每个词首 inputString[0..i-1]，检查它是否存在于字典中。如果词首存在，则将 dpTable[i] 标记为 true。

步骤 5: 如果 dpTable[i] 为 true，则检查剩余的子字符串 inputString[i..end]。继续检查并更新 DP 表中每个有效的子字符串，直到整个字符串被分割。

步骤 6: 如果 DP 表的最后一个位置 (dpTable[strLength]) 为 true，则表示成功分割，返回 true；否则，返回 false。

让我们在 Java 程序中实现上述方法。

文件名: StringSegmentation.java

import java.util.*;  
// Class to handle string segmentation
class StringSegmentation {
    // Utility function to check if a word exists in the dictionary
    static boolean isWordInDictionary(String word) {
        // Array containing words in the dictionary
        String wordsInDictionary[] = {
            "apple", "orange", "banana", "fruit", "salad", 
            "ice", "cream", "cake", "pie", "and", "go", 
            "i", "like", "mango"
        };
        // Get the size of the dictionary
        int dictSize = wordsInDictionary.length;
        // Loop through the dictionary to check if the word is present
        for (int i = 0; i < dictSize; i++) {
            // Compare each word in the dictionary with the input word
            if (wordsInDictionary[i].compareTo(word) == 0) {
                return true; // Return true if a match is found
            }
        }
        return false; // Return false if no match is found
    }
    // Function to check if the input string can be segmented into dictionary words
    static boolean canSegmentString(String inputString) {
        // Get the length of the input string
        int strLength = inputString.length();
        // If the string is empty, it can be segmented successfully
        if (strLength == 0) return true;
        // Create a DP table to store results of subproblems.
        // dpTable[i] will be true if the substring inputString[0..i] can be segmented.
        boolean[] dpTable = new boolean[strLength + 1];
        // Loop through each character in the input string to check segmentations
        for (int i = 1; i <= strLength; i++) {
            // Check if the current prefix (substring from 0 to i) can form a valid word
            if (dpTable[i] == false && isWordInDictionary(inputString.substring(0, i))) {
                dpTable[i] = true;  // Mark as true if it forms a valid word
            }
            // If the current index i can be segmented
            if (dpTable[i] == true) {
                // If we have reached the end of the string
                if (i == strLength) {
                    return true;  // Return true as the entire string can be segmented
                }
                // Loop through the remaining characters to find further segmentations
                for (int j = i + 1; j <= strLength; j++) {
                    // Check if the substring inputString[i..j] can form a valid word
                    if (dpTable[j] == false && isWordInDictionary(inputString.substring(i, j))) {
                        dpTable[j] = true;  // Mark as true if it forms a valid word
                    }
                    // If we have reached the end of the string and it can be segmented
                    if (j == strLength && dpTable[j] == true) {
                        return true;  // Return true for successful segmentation
                    }
                }
            }
        }
        // If no valid segmentation is found, return false
        return false;
    }
    // Main function to test the segmentation function with test cases
    public static void main(String[] args) {
        // Test case 1: Check segmentation for the string "ilikeapple"
        if (canSegmentString("ilikeapple")) {
            System.out.print("Yes\n");  // Output "Yes" if the string can be segmented
        } else {
            System.out.print("No\n");   // Output "No" if it cannot be segmented
        }
        // Test case 2: Check segmentation for the string "bananaicecream"
        if (canSegmentString("bananaicecream")) {
            System.out.print("Yes\n");  // Output "Yes" if the string can be segmented
        } else {
            System.out.print("No\n");   // Output "No" if it cannot be segmented
        }
        // Test case 3: Check segmentation for an empty string
        if (canSegmentString("")) {
            System.out.print("Yes\n");  // Output "Yes" as empty string can always be segmented
        } else {
            System.out.print("No\n");   // Output "No" (this case won't happen for an empty string)
        }
        // Test case 4: Check segmentation for the string "ilikelikemango"
        if (canSegmentString("ilikelikemango")) {
            System.out.print("Yes\n");  // Output "Yes" if the string can be segmented
        } else {
            System.out.print("No\n");   // Output "No" if it cannot be segmented
        }
        // Test case 5: Check segmentation for the string "appleandsalad"
        if (canSegmentString("appleandsalad")) {
            System.out.print("Yes\n");  // Output "Yes" if the string can be segmented
        } else {
            System.out.print("No\n");   // Output "No" if it cannot be segmented
        }
        // Test case 6: Check segmentation for the string "appleandsalads"
        if (canSegmentString("appleandsalads")) {
            System.out.print("Yes\n");  // Output "Yes" if the string can be segmented
        } else {
            System.out.print("No\n");   // Output "No" if it cannot be segmented
        }
    }
}   

输出

 
Yes
Yes
Yes
Yes
Yes
No

时间复杂度: O(N² * M)， 其中 N 是输入长度，M 是字典单词的平均长度。

空间复杂度: O(N)， 用于存储词首分割结果的 DP 表。

优化的动态规划方法

单词拆分问题的优化动态规划解决方案使用布尔 DP 数组来存储子字符串是否可以分割成字典单词，从而避免了冗余检查。它遍历有效的起始点，并且只处理已经有有效先前分割的子字符串，从而提高了效率。

算法

步骤 1: 创建一个大小为 n+1 的布尔数组 segmentation[]（其中 n 是输入字符串的长度）。

步骤 2: 设置 segmentation[0] = true，因为空字符串始终可以被分割。

步骤 3: 使用索引 end 从 1 到 n（字符串长度）遍历字符串。

对于每个 end，遍历所有可能的起始点，从 0 到 end - 1。
检查子字符串 str[start..end] 是否在字典中，并且 segmentation[start] 是否为 true。

步骤 4: 如果两个条件都满足，则设置 segmentation[end] = true 并中断当前 end 的内层循环。

步骤 5: 填充完 segmentation 数组后，返回 segmentation[n] 的值，以检查整个字符串是否可以被分割。

让我们在 Java 程序中实现上述方法。

文件名: WordSegmenter.java

import java.io.*;   
import java.util.*;  
class WordSegmenter {  // Defining the class WordSegmenter
    // Method to check if a string can be segmented into dictionary words
    public static boolean canSegment(String str, List<String> wordDict) {
        // Array to store segmentation results for substrings.
        // segmentation[i] is true if the substring str[0..i] can be segmented.
        boolean[] segmentation = new boolean[str.length() + 1];
        // Base case: Empty string can always be segmented
        segmentation[0] = true;
        // Outer loop: Iterate through all possible end points (1 to the length of the string)
        for (int end = 0; end <= str.length(); end++) {
            // Inner loop: Check all possible start points for substring str[start..end]
            for (int start = 0; start < end; start++) {
                // Check if substring str[start..end] is in dictionary
                // and str[0..start] can be segmented (segmentation[start] is true)
                if (segmentation[start] && wordDict.contains(str.substring(start, end))) {
                    // Mark that the substring str[0..end] can be segmented
                    segmentation[end] = true;
                    break;  // No need to check further start points for this end
                }
            }
        }
        // Return whether the entire string can be segmented
        return segmentation[str.length()];
    }
    // Main method to test the word segmentation function
    public static void main(String[] args) {
        // Initialize the dictionary of words as an array
        String[] words = {
            "apple", "banana", "pie", "orange", "pear", "fruit",
            "juice", "grape", "berry", "kiwi", "melon", "peach"
        };
        // Convert the array of words to a List
        List<String> dictionary = new ArrayList<>();
        for (String word : words) {
            dictionary.add(word);  // Add each word to the dictionary list
        }
        // Test the function with different inputs and print the results
        // Check if "applepie" can be segmented using the dictionary
        if (canSegment("applepie", dictionary)) {
            System.out.println("Yes");  // Output "Yes" if the string can be segmented
        } else {
            System.out.println("No");   // Output "No" if it cannot be segmented
        }
        // Check if "bananajuice" can be segmented
        if (canSegment("bananajuice", dictionary)) {
            System.out.println("Yes");  // Output "Yes" if the string can be segmented
        } else {
            System.out.println("No");   // Output "No" if it cannot be segmented
        }
        // Check if an empty string can be segmented (always true)
        if (canSegment("", dictionary)) {
            System.out.println("Yes");  // Output "Yes" as empty string is always segmentable
        } else {
            System.out.println("No");   // This won't be executed as empty string is always segmentable
        }
        // Check if "peachkiwi" can be segmented
        if (canSegment("peachkiwi", dictionary)) {
            System.out.println("Yes");  // Output "Yes" if the string can be segmented
        } else {
            System.out.println("No");   // Output "No" if it cannot be segmented
        }
        // Check if "appleorange" can be segmented
        if (canSegment("appleorange", dictionary)) {
            System.out.println("Yes");  // Output "Yes" if the string can be segmented
        } else {
            System.out.println("No");   // Output "No" if it cannot be segmented
        }
        // Check if "grapeberryjuice" can be segmented
        if (canSegment("grapeberryjuice", dictionary)) {
            System.out.println("Yes");  // Output "Yes" if the string can be segmented
        } else {
            System.out.println("No");   // Output "No" if it cannot be segmented
        }
    }
}   

输出

 
Yes
Yes
Yes
Yes
Yes
Yes

下一主题Java Quartz 调度器

Word Break Problem in Java

使用递归方法

算法

使用动态规划

算法

优化的动态规划方法

算法

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Java Conversion

Java Misc

Word Break Problem in Java

使用递归方法

算法

使用动态规划

算法

优化的动态规划方法

算法

相关帖子

List vs ArrayList

Java 中的 Collectors.toCollection()

Narcissistic Number in Java

Jumping Number in Java

Java 中 findElement() 和 findElements() 的区别

Java 中的直线数

Java 中的 OffsetDateTime getOffset() 方法及示例

Java 中的字符串切换

Java 中的 XOR 二进制运算符

What is programming

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器