一【题目类别】

字符串

二【题目难度】

中等

三【题目编号】

139.单词拆分

四【题目描述】

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。
注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

五【题目示例】

示例 1：
- 输入: s = “leetcode”, wordDict = [“leet”, “code”]
- 输出: true
- 解释: 返回 true 因为 “leetcode” 可以由 “leet” 和 “code” 拼接成。

示例 2：
- 输入: s = “applepenapple”, wordDict = [“apple”, “pen”]
- 输出: true
- 解释: 返回 true 因为 “applepenapple” 可以由 “apple” “pen” “apple” 拼接成。注意，你可以重复使用字典中的单词。

示例 3：
- 输入: s = “catsandog”, wordDict = [“cats”, “dog”, “sand”, “and”, “cat”]
- 输出: false

六【解题思路】

此题有难度，利用哈希表的思想
我们使用dp[i]定义字符串前i个字符组成的字符串s[0,…,i - 1]能否由题目给定的字典组成
然后从前先后计算状态转移方程，在判断的时候我们需要注意要从字符串开始一直遍历到当前位置i，使用j去遍历
如果dp[j]=true，说明前j个字符可以由题目给定的字典组成，然后再判断字符串s[j,…,i-1]能不能由题目给定的字典组成，如果能，那么dp[i]=true，反之dp[i]=false
还要注意，对于边界条件dp[0]，我们定义dp[0]=true，因为空集肯定能被题目给定的字典组成，也就是说空串是合法的，而也正因为定义dp[0]=true才能使整个动态转移方程能够运行
动态转移最后一个元素就是字符串能不能由题目给定的字典组成的结果
最后返回结果即可

七【题目提示】

1 <= s.length <= 300
1 <= wordDict.length <= 1000
1 <= wordDict[i].length <= 20
s 和 wordDict[i] 仅有小写英文字母组成
wordDict 中的所有字符串互不相同

八【时间频度】

时间复杂度： $O(n^2)$ ，其中 $n$ 是字符串的长度
空间复杂度： $O (n)$ ，其中 $n$ 是字符串的长度

九【代码实现】

Java语言版

package String;

import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class p139_WordBreak {

    public static void main(String[] args) {
        String s = "leetcode";
        List<String> wordDict = Arrays.asList(new String[]{"leet", "code"});
        boolean res = wordBreak(s, wordDict);
        System.out.println("res = " + res);
    }

    public static boolean wordBreak(String s, List<String> wordDict) {
        Set<String> wordDictSet = new HashSet(wordDict);
        int lenS = s.length();
        boolean[] dp = new boolean[lenS + 1];
        dp[0] = true;
        for (int i = 1; i <= lenS; i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && wordDictSet.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[lenS];
    }

}

C语言版

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<stdbool.h>

unsigned long long Hash(char* s, int l, int r)
{
	unsigned long long value = 0;
	for (int i = l; i < r; i++)
	{
		value = value * 2333ull;
		value += s[i] - 'a' + 1;
	}
	return value;
}

bool query(unsigned long long *rec, int recLen, unsigned long long x)
{
	for (int i = 0; i < recLen; i++)
	{
		if (rec[i] == x)
		{
			return true;
		}
	}
	return false;
}

bool wordBreak(char * s, char ** wordDict, int wordDictSize)
{
	unsigned long long* rec = (unsigned long long*)malloc(sizeof(unsigned long long) * wordDictSize);
	for (int i = 0; i < wordDictSize; i++)
	{
		rec[i] = Hash(wordDict[i], 0, strlen(wordDict[i]));
	}
	int lenS = strlen(s);
	bool *dp = (bool *)calloc(lenS + 1, sizeof(bool));
	dp[0] = true;
	for (int i = 1; i <= lenS; i++)
	{
		for (int j = 0; j < i; j++)
		{
			if (dp[j] && query(rec, wordDictSize, Hash(s, j, i)))
			{
				dp[i] = true;
				break;
			}
		}
	}
	return dp[lenS];
}

/*主函数省略*/