[LintCode/LeetCode] Word Break

dunizb 發(fā)布于2019-08-14 15:30 / 670人閱讀

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

基礎動規(guī)題目，有幾個細節(jié)要注意。dp[0]是指，當s為空的時候的word-dict映射布爾值；另外，循環(huán)s第i個字符的時候，若該位已經(jīng)判斷過沒有映射在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

文章版權歸作者所有，未經(jīng)允許請勿轉載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉載請注明本文地址：http://m.hztianpu.com/yun/65810.html

[LintCode/LeetCode] Implement Trie

摘要：首先，我們應該了解字典樹的性質和結構，就會很容易實現(xiàn)要求的三個相似的功能插入，查找，前綴查找。既然叫做字典樹，它一定具有順序存放個字母的性質。所以，在字典樹的里面，添加，和三個參數(shù)。 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

摘要：構造數(shù)組，是的，是的，是將位的轉換成位的需要的步數(shù)。初始化和為到它們各自的距離，然后兩次循環(huán)和即可。 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

摘要：和完全一樣的做法，只要在初始化首行和首列遇到時置零且即可。對了，數(shù)組其它元素遇到也要置零喏，不過就不要啦。 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

摘要：首先將兩個字符串化成字符數(shù)組，排序后逐位比較，確定它們等長且具有相同數(shù)量的相同字符。然后，從第一個字符開始向后遍歷，判斷和中以這個坐標為中點的左右兩個子字符串是否滿足第一步中互為的條件設分為和，分為和。 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