findingsea's Studio.

Word Break I II@LeetCode

LeetCode
Word count: 390 / Reading time: 2 min
2015/04/26 Share

Word Break

递归，基本属于暴力求解。但是纯暴力应该是过不了的，参考网上的办法，增加了一个unmatch集合，类型是HashSet，用来存放那些已经被验证过无法匹配的字符串，这样可以剪掉很多分支。

实现代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Solution {
    private Set<String> unmatch = new HashSet<String>();

    public boolean wordBreak(String s, Set<String> dict) {
        for (String prefix : dict) {
            if (s.equals(prefix))
                return true;
            if (s.startsWith(prefix)) {
                String suffix = s.substring(prefix.length(), s.length());
                if (!unmatch.contains(suffix)) {
                    if (wordBreak(suffix, dict))
                        return true;
                    else
                        unmatch.add(suffix);
                }
            }
        }
        return false;
    }
}

Word Break II

解法基本差不多，无非是增加记录路径的要求。这里唯一需要注意的是，在前面我们只要一找到符合条件的组合即可返回了，在这题中，一定要遍历所有情况之后再返回。当然，还是用了一个mismatch来剪分支。

实现代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
public class Solution {
    public List<String> wordBreak(String s, Set<String> dict) {
        List<String> result = new LinkedList<String>();
        if (s.length() == 0)
            return result;
        generate(s, dict, new HashSet<String>(), result, new StringBuilder());
        return result;
    }

    private boolean generate(String s, Set<String> dict, Set<String> mismatch,
                             List<String> result, StringBuilder sentence) {
        if (s.length() == 0) {
            result.add(sentence.toString());
            return true;
        }
        boolean canBreak = false;
        for (String word : dict) {
            if (s.startsWith(word)) {
                String suffix = s.substring(word.length(), s.length());
                if (!mismatch.contains(suffix)) {
                    StringBuilder newSentence = new StringBuilder(sentence);
                    if (newSentence.length() != 0) newSentence.append(" ");
                    newSentence.append(word);
                    if (generate(suffix, dict, mismatch,
                            result, newSentence)) {
                        canBreak = true;
                    } else {
                        mismatch.add(suffix);
                    }
                }
            }
        }
        return canBreak;
    }
}

原文作者: findingsea

原文链接: http://findingsea.github.io/2015/04/26/word-break-i-ii-at-leetcode/

发表日期: April 26th 2015, 9:32:00 am

版权声明: 本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
  1. 1. Word Break
  2. 2. Word Break II
Total : 100
2020
2019
2018
2017
2015
2014
2013
Octopress GitHub Python Django 吐槽 Reading ACM 项目总结 JavaScript 日志 Java LeetCode Interview Algorithm Life Windows ffmpeg life Go c++ essay review