国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

[LintCode/LeetCode] Word Break

dunizb / 601人閱讀

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

基礎(chǔ)動(dòng)規(guī)題目，有幾個(gè)細(xì)節(jié)要注意。dp[0]是指，當(dāng)s為空的時(shí)候的word-dict映射布爾值；另外，循環(huán)s第i個(gè)字符的時(shí)候，若該位已經(jīng)判斷過沒有映射在dict中的word，就跳過；若這一位開始，加上從dict中取詞的長度越界，則跳過；若dict中的取詞和這一位起始的子字符串相等，則給子字符串的最后一個(gè)字符映射的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];
    }
}

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

轉(zhuǎn)載請(qǐng)注明本文地址：http://specialneedsforspecialkids.com/yun/65810.html

相關(guān)文章

  • [LintCode/LeetCode] Implement Trie

    摘要：首先，我們應(yīng)該了解字典樹的性質(zhì)和結(jié)構(gòu)，就會(huì)很容易實(shí)現(xiàn)要求的三個(gè)相似的功能插入，查找，前綴查找。既然叫做字典樹，它一定具有順序存放個(gè)字母的性質(zhì)。所以，在字典樹的里面，添加，和三個(gè)參數(shù)。 Problem Implement a trie with insert, search, and startsWith methods. Notice You may assume that all i...

    付永剛 評(píng)論0 收藏0

  • [LintCode/LeetCode] Edit Distance

    摘要：構(gòu)造數(shù)組，是的，是的，是將位的轉(zhuǎn)換成位的需要的步數(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 評(píng)論0 收藏0

  • [LintCode/LeetCode] Unique Paths II

    摘要：和完全一樣的做法，只要在初始化首行和首列遇到時(shí)置零且即可。對(duì)了，數(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 評(píng)論0 收藏0

  • [LintCode/LeetCode] Restore IP Addresses

    摘要：第一個(gè)分割點(diǎn)第二個(gè)分割點(diǎn)第三個(gè)分割點(diǎn) 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 評(píng)論0 收藏0

  • [LintCode/LeetCode] Scramble String

    摘要：首先將兩個(gè)字符串化成字符數(shù)組，排序后逐位比較，確定它們等長且具有相同數(shù)量的相同字符。然后，從第一個(gè)字符開始向后遍歷，判斷和中以這個(gè)坐標(biāo)為中點(diǎn)的左右兩個(gè)子字符串是否滿足第一步中互為的條件設(shè)分為和，分為和。 Problem Given a string s1, we may represent it as a binary tree by partitioning it to two no...

    MASAILA 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<