单词拆分

发表于
本文字数： 857 阅读时长 ≈ 1 分钟

LeetCode每日一题，139.Word Break

先看题目描述

大意就是判断能否用 wordDict 里的单词拼接出字符串 s

算法和思路

动态规划

我们定义 dp[i] 表示字符串 s 前 i 个字符组成的字符串 s[0..i-1 是否能被空格拆分成若干个字典中出现的单词

经分析可得到状态转移方程为: dp[i] = dp[j] && check(s[j…i - 1])

根据状态转移方程就可以实现算法源码，为了优化算法，可统计待选字符串中最长字符串的长度，以减少无用访问

算法源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import java.util.*;

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        int max = 0;
        for (String word: wordDict) {
            max = Math.max(max, word.length());
        }
        boolean dp[] = new boolean[s.length() + 1];
        dp[0] = true;
        for (int i = 1; i <= s.length(); i++) {
            for (int j = Math.max(0, i - max); j < i; j++) {
                if (dp[i] = dp[j] && wordDict.contains(s.substring(j, i))) break;
            }
        }
        return dp[s.length()];
    }
}