关于java:LeetCode139单词拆分

4次阅读

共计 1898 个字符，预计需要花费 5 分钟才能阅读完成。

题目形容：给定一个非空字符串 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));
    }
}