java如何實(shí)現(xiàn)單詞拆分

這篇文章主要為大家展示了java如何實(shí)現(xiàn)單詞拆分，內(nèi)容簡(jiǎn)而易懂，條理清晰，希望能夠幫助大家解決疑惑，下面讓小編帶大家一起來研究并學(xué)習(xí)一下“java如何實(shí)現(xiàn)單詞拆分”這篇文章吧。

給定一個(gè)非空字符串 s 和一個(gè)包含非空單詞列表的字典 wordDict，判定 s 是否可以被空格拆分為一個(gè)或多個(gè)在字典中出現(xiàn)的單詞。

說明：

• 拆分時(shí)可以重復(fù)使用字典中的單詞。

• 你可以假設(shè)字典中沒有重復(fù)的單詞。

示例 1：

輸入: s = "leetcode", wordDict = ["leet", "code"]
輸出: true
解釋: 返回 true 因?yàn)?"leetcode" 可以被拆分成 "leet code"。

示例 2：

輸入: s = "applepenapple", wordDict = ["apple", "pen"]
輸出: true
解釋: 返回 true 因?yàn)?"applepenapple" 可以被拆分成 "apple pen apple"。
注意你可以重復(fù)使用字典中的單詞。

示例 3：

輸入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
輸出: false

答案：

 1public boolean wordBreak(String s, List<String> wordDict) {
 2    int len = s.length();
 3    boolean[] f = new boolean[len + 1];
 4    f[0] = true;
 5    for (int i = 1; i < len + 1; i++)
 6        for (int j = 0; j < i; j++)
 7            if (f[j] && wordDict.contains(s.substring(j, i))) {
 8                f[i] = true;
 9                break;
10            }
11    return f[len];
12}

解析：

f[n]表示前n個(gè)字符可以拆分成功。上面代碼第7行如果成立就表示前j個(gè)字符可以拆分成功并且字符串的j到i拆分成的字符串在wordDict中存在，所以字符串的前i個(gè)都能拆分成功。代碼比較簡(jiǎn)單，很容易理解，下面來看一個(gè)遞歸的寫法

 1public boolean wordBreak(String s, List<String> wordDict) {
 2    return wordBreakHelper(s, new HashSet(wordDict), 0);
 3}
 4
 5public boolean wordBreakHelper(String s, Set<String> wordDict, int start) {
 6    if (start == s.length())
 7        return true;
 8    for (int end = start + 1; end <= s.length(); end++) {
 9        if (wordDict.contains(s.substring(start, end)) && wordBreakHelper(s, wordDict, end))
10            return true;
11    }
12    return false;
13}

這種解法應(yīng)該比上面一種更容易理解，其中workBreadhelper（String s,set<String> wordDict，int start）如果返回true，則表示字符串s從位置start到s.length()都可以拆分成功。但這種說法效率不是很高，有可能會(huì)超時(shí)，有興趣的大家可以優(yōu)化一下

Java的特點(diǎn)有哪些

Java的特點(diǎn)有哪些 1.Java語言作為靜態(tài)面向?qū)ο缶幊陶Z言的代表，實(shí)現(xiàn)了面向?qū)ο罄碚摚试S程序員以優(yōu)雅的思維方式進(jìn)行復(fù)雜的編程。 2.Java具有簡(jiǎn)單性、面向?qū)ο?、分布式、安全性、平臺(tái)獨(dú)立與可移植性、動(dòng)態(tài)性等特點(diǎn)。 3.使用Java可以編寫桌面應(yīng)用程序、Web應(yīng)用程序、分布式系統(tǒng)和嵌入式系統(tǒng)應(yīng)用程序等。

以上就是關(guān)于“java如何實(shí)現(xiàn)單詞拆分”的內(nèi)容，如果該文章對(duì)您有所幫助并覺得寫得不錯(cuò)，勞請(qǐng)分享給您的好友一起學(xué)習(xí)新知識(shí)，若想了解更多相關(guān)知識(shí)內(nèi)容，請(qǐng)多多關(guān)注億速云行業(yè)資訊頻道。