word break

senntyou 發布于2019-08-16 10:33 / 3436人閱讀

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented 
into a space-separated sequence of one or more dictionary words. You may assume the dictionary does not contain duplicate words.

For example, given
s = "leetcode",
dict = ["leet", "code"].

Return true because "leetcode" can be segmented as "leet code".

public class Solution {
    // shoudl consider input, wordDict is small, check through string s
    //  O(n*m)  m for small Dict
    public boolean wordBreak(String s, List wordDict) {
        boolean[] canBreak = new boolean[s.length() + 1]; // s can be break from start to i;
        canBreak[0] = true;
        
        for(int i=0; i<= s.length(); i++){
            if(!canBreak[i]) continue;
            
            for(String word : wordDict) {   // renew each possible position with true
                int len = word.length();
                int end = i + len;
                // those unreachable position and reached position should ignore
                if(end > s.length() || canBreak[end]) continue;
                
                if(s.substring(i,end).equals(word)){
                    canBreak[end] = true;
                }
            }
        }
        
        return canBreak[s.length()];
    }
}

/*
//Second DP
        put list into Set           
        O(n^2) time two nested for loop
        O(K) for Dict
        for(int i=1; i <= s.length(); i++){         // fix the ending, find the starting, then compare middle
            for(int j=0; j < i; j++){
                if(f[j] && dict.contains(s.substring(j, i))){
                    f[i] = true;
                    break;
                }
            }
        }
*/

GPU云服務器云服務器 break-word word-break breaks break

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

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

white-space、word-wrap和word-break的簡單整理

摘要：理解和的區別從易于區分和理解的角度，我引用了無雙在你真的了解和的區別嗎一文中對兩個屬性作用的解釋屬性用來標明是否允許瀏覽器在單詞內進行斷句，這是為了防止當一個字符串太長而找不到它的自然斷句點時產生溢出現象。 white-space 、 word-wrap 和 word-break 是決定段落中的文本如何展示的3個css屬性，屬性說明請點擊鏈接查看參考手冊。 white-space wh...

Magicer 2019-08-30 15:52 評論0 收藏0
文字處理之二：換行及word-break和word-wrap屬性

摘要：英文換行來到英文，情況就要復雜一些。在英文中有單詞的概念，所以在換行時就得考慮單詞的完整性。上面介紹的值，主要也是針對英文的，漢字還是按照瀏覽器的默認行為，裝不下就換行。最后顯示時，英文還是按照默認行為，中文變成了不換行。上一篇博客中介紹white-space屬性時聊到了換行，這一篇介紹換行的細節。瀏覽器的默認行為瀏覽器的換行行為，對于中文和英文存在一些差別。中文換行正如上一...

wangxinarhat 2019-08-30 15:44 評論0 收藏0
GO111MODEDULE變量以及Go Module的使用建議

我們可能在很多地方如 README 文件、Makefile 文件以及 Dockerfile 文件中看到GO111MODULE=on，對于剛接觸的Golang的開發者可能對此有很多疑惑。這片文章，我將詳細介紹GO111MODULE變量的意義，以及什么時候需要使用到該變量，同時也總結了一些在使用 Go Modules 時需要注意的細節，幫助你在下次遇到這個變量時不再疑惑。GO111MODULE=o...

社區管理員 2022-10-08 14:07 評論0 收藏0
高性價比GPU算力平臺推薦，4090僅需2.6元/小時，開沖！

ChatGPT和Sora等AI大模型應用，將AI大模型和算力需求的熱度不斷帶上新的臺階。哪里可以獲得廉價算力，進行AI視頻生成等模型開發和應用呢？Compshare是隸屬于UCloud云計算的GPU算力平臺，專注提供高性價比的NVIDIA RTX 40 系列資源，滿足 AI應用、模型推理/微調、科學計算等多場景需要。UCloud本身是一家專注于公有云的云計算廠商，成立于2012年，是中國第一家科創...

UCloud小助手 2024-05-14 11:33 評論0 收藏0