Word Break

原题: https://leetcode.com/problems/word-break/description/

题意: 给定一个字符串s和一个单词的字典dict,判断s是否可以分隔成由一个或多个字典中的单词组成的序列。

例子: 
给定:
s = "leetcode",
dict = ["leet", "code"].

返回:true
标签: dict、word、成由、leet、字典、面试
猜你感兴趣的圈子:
LeetCode交流圈
  • Bingo
    2017-08-14 17:44:50 1楼#1层
    Python解法一:
    class Solution:
        # @param s, a string
        # @param wordDict, a set<string>
        # @return a boolean
        def wordBreak(self, s, wordDict):
            queue = [s]
            visitSet = set([s])
            while queue:
                front = queue.pop(0)
                if front in wordDict:
                    return True
                prefix = ''
                for c in front:
                    prefix += c
                    suffix = front[len(prefix):]
                    if prefix in wordDict and suffix not in visitSet:
                        queue.append(suffix)
                        visitSet.add(suffix)
            return False
  • Bingo
    2017-08-14 17:45:07 2楼#1层
    Python解法二:
    class Solution:
        # @param s, a string
        # @param wordDict, a set<string>
        # @return a boolean
        def wordBreak(self, s, words):
            ok = [True]
            for i in range(1, len(s)+1):
                ok += any(ok[j] and s[j:i] in words for j in range(i)),
            return ok[-1]
  • Bingo
    2017-08-14 17:48:20 3楼#1层
    Java:
    public class Solution {
        public boolean wordBreak(String s, Set<String> wordDict) {
            boolean[] dp = new boolean[s.length()+1];
            Arrays.fill(dp,false);
            dp[s.length()]=true;
            // 外层循环递增长度
            for(int i = s.length()-1; i >=0 ; i--){
                // 内层循环寻找分割点
                for(int j = i; j < s.length(); j++){
                    String sub = s.substring(i,j+1);
                    if(wordDict.contains(sub) && dp[j+1]){
                        dp[i] = true;
                        break;
                    }
                }
            }
            return dp[0];
        }
    }
  • 回复
隐藏