[LintCode/LeetCode] Word Break

dunizb 发布于2019-08-14 15:30 / 566人阅读

Problem

Given a string s and a dictionary of words dict, determine if s can be break into a space-separated sequence of one or more dictionary words.

Example

Given s = "lintcode", dict = ["lint", "code"].

Return true because "lintcode" can be break as "lint code".

Note

基础动规题目，有几个细节要注意。dp[0]是指，当s为空的时候的word-dict映射布尔值；另外，循环s第i个字符的时候，若该位已经判断过没有映射在dict中的word，就跳过；若这一位开始，加上从dict中取词的长度越界，则跳过；若dict中的取词和这一位起始的子字符串相等，则给子字符串的最后一个字符映射的dp[j]赋true。

Solution

public class Solution {
    public boolean wordBreak(String s, Set dict) {
        int n = s.length();
        boolean[] dp = new boolean[n+1];
        dp[0] = true;
        for (int i = 0; i < n; i++) {
            if (!dp[i]) continue;
            for (String word: dict) {
                int l = word.length(), j = i + l;
                if (j > n || dp[j]) continue;
                if (word.equals(s.substring(i, j))) dp[j] = true;
            }
        }
        return dp[n];
    }
}

Update 2018-9

class Solution {
    public boolean wordBreak(String s, List wordDict) {
        Set dict = new HashSet<>(wordDict);
        int n = s.length();
        boolean[] dp = new boolean[n+1];
        dp[0] = true;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && dict.contains(s.substring(j, i))) dp[i] = true;
            }
        }
        return dp[n];
    }
}

GPU云服务器云服务器 break-word word-break break 语言 break

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/65810.html

[LintCode/LeetCode] Implement Trie

摘要：首先，我们应该了解字典树的性质和结构，就会很容易实现要求的三个相似的功能插入，查找，前缀查找。既然叫做字典树，它一定具有顺序存放个字母的性质。所以，在字典树的里面，添加，和三个参数。 Problem Implement a trie with insert, search, and startsWith methods. Notice You may assume that all i...

付永刚 2019-08-14 15:23 评论0 收藏0
[LintCode/LeetCode] Edit Distance

摘要：构造数组，是的，是的，是将位的转换成位的需要的步数。初始化和为到它们各自的距离，然后两次循环和即可。 Problem Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 s...

snowell 2019-08-14 15:29 评论0 收藏0
[LintCode/LeetCode] Unique Paths II

摘要：和完全一样的做法，只要在初始化首行和首列遇到时置零且即可。对了，数组其它元素遇到也要置零喏，不过就不要啦。 Problem Follow up for Unique Paths: Now consider if some obstacles are added to the grids. How many unique paths would there be? An obstacle...

firim 2019-08-14 15:29 评论0 收藏0
[LintCode/LeetCode] Restore IP Addresses

摘要：第一个分割点第二个分割点第三个分割点 Problem Given a string containing only digits, restore it by returning all possible valid IP address combinations. Example Given 25525511135, return [ 255.255.11.135, 255....

bingo 2019-08-14 15:14 评论0 收藏0
[LintCode/LeetCode] Scramble String

摘要：首先将两个字符串化成字符数组，排序后逐位比较，确定它们等长且具有相同数量的相同字符。然后，从第一个字符开始向后遍历，判断和中以这个坐标为中点的左右两个子字符串是否满足第一步中互为的条件设分为和，分为和。 Problem Given a string s1, we may represent it as a binary tree by partitioning it to two no...

MASAILA 2019-08-14 15:45 评论0 收藏0