单词拆分

题目形容：给定一个非空字符串 s 和一个蕴含非空单词的列表 wordDict，断定 s 是否能够被空格拆分为一个或多个在字典中呈现的单词。

阐明：

  • 拆分时能够重复使用字典中的单词。
  • 你能够假如字典中没有反复的单词。

示例阐明请见LeetCode官网。

起源：力扣（LeetCode）
链接：https://leetcode-cn.com/probl...
著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。

解法一：穷举法

应用穷举+递归的形式求解，效率较低，具体处理过程如下：

  • 如果以后字符串为null或者为空字符串，则默认能够由字符串字典切分，间接返回true；

  • 否则，遍历字符串字典中的字符串：

    • 如果某个字符串刚好和以后字符串相等并且长度统一，则间接返回true；
    • 如果某个字符串和以后字符串相等然而长度不统一，递归判断前面的字符串并返回判断的后果。
  • 最初，返回最终判断的后果。
解法二：动静布局
  • 首先，初始化字符串字典到哈希表wordDictSet中，便于疾速查找；
  • 而后初始化一个dp数组，数组的长度为原始字符串的长度加1，并初始化数组的第一个元素为true；

  • 而后遍历字符串，判断从0到i的字符串是否能够由字符串字典切分而成：

    • 判断逻辑是从0到j的字符串能够由字符串字典切分（这个依据后面的计算失去） 并且 从j到i 的字符串在字符串字典中。
  • 最终，返回dp数组的最初一个元素即为最终后果。
import java.util.ArrayList;import java.util.HashSet;import java.util.List;import java.util.Set;public class LeetCode_139 {    private static boolean flag = false;    /**     * 穷举法     *     * @param s     * @param wordDict     * @return     */    public static boolean wordBreak(String s, List<String> wordDict) {        if (s == null || s.length() == 0) {            return true;        }        for (String word : wordDict) {            if (flag) {                return flag;            }            if (s.startsWith(word)) {                if (s.length() == word.length()) {                    // 如果以后字符与字符串字典中的某个字符串匹配并且长度雷同，则阐明以后字符串能够由字符串字典切分成，返回true                    return true;                }                // 如果以后字符串由某个字符串字典中的字符串切分后，还有待判断的字符，则递归判断前面的字符串                flag = wordBreak(s.substring(word.length()), wordDict);            }        }        return flag;    }    /**     * 动静布局     *     * @param s     * @param wordDict     * @return     */    public static boolean wordBreak2(String s, List<String> wordDict) {        // 初始化字符串字典到哈希表中，便于疾速查找        Set<String> wordDictSet = new HashSet<>(wordDict);        boolean[] dp = new boolean[s.length() + 1];        // 默认空字符串能够由字符串字典切分而成，初始置为true        dp[0] = true;        // 判断从0到i的字符串是否能够由字符串字典切分而成        for (int i = 1; i <= s.length(); i++) {            for (int j = 0; j < i; j++) {                // 判断逻辑是从0到j的字符串能够由字符串字典切分（这个依据后面的计算失去） 并且 从j到i 的字符串在字符串字典中                if (dp[j] && wordDictSet.contains(s.substring(j, i))) {                    dp[i] = true;                    break;                }            }        }        return dp[s.length()];    }    public static void main(String[] args) {        String s = "applepenapple";        List<String> wordDict = new ArrayList<>();        wordDict.add("apple");        wordDict.add("pen");        System.out.println(wordBreak(s, wordDict));        System.out.println(wordBreak2(s, wordDict));    }}
【每日寄语】 要置信机会总是会有的，不要和本人较劲，要趁势，像太极推手一样，趁势而为，要学会利用周边资源。