Java算法题-解析单词拆分问题

题目

给定一个非空字符串 s 和一个包含非空单词的字典，判断 s 是否可以被拆分成字典中的单词。你可以假设字典中没有重复的单词。

引言

在这个算法问题中，我们将探讨一个与字符串处理相关的经典动态规划挑战。问题的核心是判断一个给定字符串是否可以被拆分成一个或多个字典中存在的单词。

算法思路

为了解决这个问题，我们可以使用动态规划。我们创建一个大小为 n + 1 的数组 dp，其中 n 是输入字符串的长度。dp[i] 表示从索引 0 到 i - 1（包括 i - 1）的子字符串是否可以被拆分成字典中的单词。我们遍历输入字符串，并检查以索引 i 结尾的子字符串是否可以在字典中找到。如果可以，我们将 dp[i + 1] 设为 true。最终的答案将是 dp[n]。

代码实现

以下是使用Java实现的解决方案：

import java.util.List;

public class WordBreak {
    public boolean wordBreak(String s, List<String> wordDict) {
        int n = s.length();
        boolean[] dp = new boolean[n + 1];
        dp[0] = true;

        for (int i = 1; i <= n; i++) {
            for (String word : wordDict) {
                if (i >= word.length() && dp[i - word.length()] && s.substring(i - word.length(), i).equals(word)) {
                    dp[i] = true;
                    break;
                }
            }
        }

        return dp[n];
    }
}

算法分析

• 时间复杂度：外部循环运行了 n 次，内部循环运行了 m 次，其中 n 是输入字符串的长度，m 是字典的大小。因此，总的时间复杂度为 O(n * m)。
• 空间复杂度：算法使用了额外的大小为 n + 1 的布尔数组 dp，因此空间复杂度为 O(n)。

示例和测试

你可以使用以下代码来测试算法：

import java.util.Arrays;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        WordBreak solution = new WordBreak();
        String s = "leetcode";
        List<String> wordDict = Arrays.asList("leet", "code");

        boolean canBreak = solution.wordBreak(s, wordDict);
        System.out.println("输入字符串是否可以被拆分？ " + canBreak);
    }
}

总结

单词拆分问题是一个经典的动态规划挑战。通过运用动态规划，我们能够高效地判断给定字符串是否可以被拆分成字典中的单词。熟悉并掌握动态规划的概念对于解决类似问题非常重要。