题目解析:给定一个连续字符串s和一个单词字典列表wordDict,判断s是否能够通过空格拆分为一个或多个字典中的单词。
说明:
拆分过程中字典中的单词可以重复使用。
字典中的单词不会重复。
解题思路一:穷举+递归
这种方法的效率相对较低。具体步骤如下:
1. 若当前字符串为空,则默认可以由字典切分,直接返回true。
2. 遍历字典中的每个单词,尝试与当前字符串进行匹配。
3. 若找到匹配的单词,且长度一致,则返回true;若长度不一致,则递归检查剩余字符串。
4. 若未找到匹配项,则返回递归结果。
解题思路二:动态规划(DP)
为了提升效率,可以采用动态规划的方法。具体步骤如下:
1. 将字典中的单词存入哈希表wordDictSet中,便于快速查找。
2. 初始化一个dp数组,数组长度为原始字符串的长度加1,其中第一个元素设为true。这表示空字符串可以被切分。
3. 遍历原始字符串,对于每个位置i,检查从0到i的字符串是否可由字典切分而成。这需要满足两个条件:从0到j的字符串可以被切分(根据前面的计算结果),并且从j到i的字符串在字典中。这里的j是i的前一个位置。
4. dp数组的最后一个元素即为最终结果,表示整个字符串s是否可以被切分。
每日寄语:相信机会总是存在的,不要过于固执己见。学会顺势而为,像太极推手一样灵活利用周边资源,成就更好的自己。