leetcode----139. Word Break-白红宇

leetcode----139. Word Break

阅读量：4112 次

发布时间：2019-05-25

本文共 5791 字，大约阅读时间需要 19 分钟。

链接：

大意：

给定一个字符串s，以及一个字典wordDict。判断s被进行n次分段后，每个分段的word是否都存在于wordDict。

思路：

首先想到的是一种使用dfs的方法，但是最终超时了。。。

具体步骤为：

使用一个256长度的TreeSet数组treeSets，每个元素都是TreeSet（TreeSet中的元素按长度排序）

将wordDict中的单词按照首字母，将其添加到treeSets的对应位置

对于s的当前遍历位置i，取到在字典中以s.charAt(i)开头的字符串所在的treeSet[s.charAt(i)]。依次对比treeSet[s.charAt(i)]中的元素str和s.substring(i,i + str.length());

如果equals并且 i + str.length() == s.length() 则可以找到一种分割使得满足题意

如果equals但是 i + str.length() < s.length() 则s从i + str.length() 开始继续往后走

如果不相等，则与treeSet[s.charAt(i)]中的下一个元素比较

代码：（超时）

class Solution {    private boolean res = false; // 用于判断结果的boolean    public boolean wordBreak(String s, List
   
     wordDict) {        TreeSet
    
     [] treeSets = new TreeSet[256]; // 共可能有256种字符        for (int i = 0; i < 256; i++) {            treeSets[i] = new TreeSet<>(new Comparator
     
      (){                public int compare(String s1, String s2) {                    return s1.length() - s2.length() == 0 ? 1 : s1.length() - s2.length(); // 坚决不能返回0  否则两个长度一样的字符串会被认为是相同的                }            }); // 第i个treeSet存储开头字母为(char) i 的word，并且在同一个treeSet中按照word的length从小到大排列        }        // 将每个单词添加到对应的treeSet中        for (String str : wordDict) {            treeSets[str.charAt(0)].add(str);        }        wordBreak(s, 0, treeSets);        return res;    }    // start为当前待比较的s子串的起始位置     public void wordBreak(String s, int start, TreeSet
      
       [] treeSets) {        TreeSet
       
         treeSet = treeSets[s.charAt(start)];        int len = s.length();        for (String str : treeSet) {            // 剪枝            if (start + str.length() > len)                return ;            // 找到s的某一子串存在于字典中            if (s.substring(start, start + str.length()).equals(str)) {                // System.out.println(start + ":" + str);                if (start + str.length() == len) {                    res = true;                    return ;                }                wordBreak(s, start + str.length(), treeSets);                if (res) // 快速结束战斗                    return ;            }        }    }}

结果：

结论：

既然超时，那就得另寻他法。

改进一：

查看了 Related Topics之后，提示用动态规划解决（感觉自己还是好弱，无法第一时间想到最优解法...）。于是就写了个动归的解法：

class Solution {    public boolean wordBreak(String s, List
   
     wordDict) {        Set
    
      set = new HashSet<>(wordDict); // 将List转为Set 查找更高效        boolean[][] dp = new boolean[s.length()][s.length()]; // dp[i][j] : s.substring(i, j + 1)是否满足题意        // 从后往前        for (int i = s.length() - 1; i >= 0; i--) {            for (int j = i; j < s.length(); j++) {                if (i == s.length() - 1) {                    dp[i][j] = set.contains(s.substring(i, j + 1)); // 最后一个字符                } else {                    // dp[i][s.length() - 1] = set.contains(s.substring(i, j + 1)) && dp[j + 1][s.length() - 1]                    if (j < s.length() - 1) {                        if (set.contains(s.substring(i, j + 1)) && dp[j + 1][s.length() - 1]) {                            dp[i][s.length() - 1] = true;                            break;                        }                        } else {                        dp[i][s.length() - 1] = set.contains(s.substring(i, s.length()));                    }                }            }        }        return dp[0][s.length() - 1];    }}

效率低下，再改！！！

改进二：

感觉可以把二维数组变为一位数组。其中 dp[i] 意为：s.substring(0,i + 1)是否满足题意。则最终需要返回的即是 dp[s.length() - 1] . 并且发现不经过List-》Set这一步之后，时间效率提高了（可能是因为字典中单词太少的缘故...）代码：

class Solution {    public boolean wordBreak(String s, List
   
     wordDict) {        // Set
    
      set = new HashSet<>(wordDict); // 将List转为Set 查找更高效        boolean[] dp = new boolean[s.length()]; // dp[i] : s.substring(0, i + 1)是否满足题意        // 从前往后        for (int i = 0; i < s.length(); i++) {            for (int j = 0; j <= i; j++) {                if (i == 0) {                    dp[i] = wordDict.contains(s.substring(i, j + 1)); // 最后一个字符                } else {                    // 递推公式：dp[i] = set.contains(s.substring(j + 1, i + 1)) && dp[j]                    if (j < i) {                        if (wordDict.contains(s.substring(j + 1, i + 1)) && dp[j]) {                            dp[i] = true;                            break;                        }                        } else {                        dp[i] = wordDict.contains(s.substring(0, i + 1));                    }                }            }        }        return dp[s.length() - 1];    }}

改进三：

针对测试用例的一些特殊用例，增加一个快速判断不存在满足题意的分割的情况，即：若s中某一字符未出现在字典中任何一个字符串之中，则直接返回false

class Solution {    public boolean wordBreak(String s, List
   
     wordDict) {        boolean[] dp = new boolean[s.length()]; // dp[i] : s.substring(0, i + 1)是否满足题意        // 快速判断无法分割的情况        Set
    
      chars1 = new HashSet<>();        for (String str : wordDict) {            for (char c : str.toCharArray()) {                chars1.add(c);            }        }        for (char c : s.toCharArray()) {            if (!chars1.contains(c))                return false;        }        // 从前往后        for (int i = 0; i < s.length(); i++) {            for (int j = 0; j <= i; j++) {                if (i == 0) {                    dp[i] = wordDict.contains(s.substring(i, j + 1)); // 最后一个字符                } else {                    // 递推公式：dp[i] = set.contains(s.substring(j + 1, i + 1)) && dp[j]                    if (j < i) {                        if (wordDict.contains(s.substring(j + 1, i + 1)) && dp[j]) {                            dp[i] = true;                            break;                        }                        } else {                        dp[i] = wordDict.contains(s.substring(0, i + 1));                    }                }            }        }        return dp[s.length() - 1];    }}

最终结论：

关键点还是动态规划，即改进一中的思路能想到就没有问题。改进二和改进三都属于优化环节。。。

菜鸡好菜啊。。。

转载地址：http://pxesi.baihongyu.com/

你可能感兴趣的文章