LeetCode 139. 单词拆分

题目描述

🔥 139. 单词拆分

思路分析

完全背包排列问题

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

func wordBreak(s string, wordDict []string) bool {
	wordSet := make(map[string]bool)
	for _, word := range wordDict {
		wordSet[word] = true
	}
	n := len(s)
	// dp[i] 表示字符串 s[0:i] 是否可以被拆分成字典中的单词
	dp := make([]bool, n+1)
	dp[0] = true

	for i := 1; i <= n; i++ {
		for j := 0; j < i; j++ {
			if dp[j] && wordSet[s[j:i]] {
				dp[i] = true
				break
			}
		}
	}
	return dp[n]
}

🍏 点击查看 Java 题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> wordSet = new HashSet<>(wordDict);
        boolean[] dp = new boolean[s.length() + 1]; // dp[i] 表示 s 的前 i 个字符是否可以被拆分成字典中的单词
        dp[0] = true;
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && wordSet.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }
}
本文作者:
本文链接: https://hgnulb.github.io/blog/2022/14966021
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！