摘要:所以現在里面應該存可以使長度為所有可能的里的最后一個。有兩種寫法,一個就是直接寫成數組的形式,不能形成的。結束之后,第二步就是通過里面保存的,一步一步回溯找到所有結果。直接的會超時,考慮記憶化搜索。所以事先對排序。
Word Break
鏈接:https://leetcode.com/problems...
這種找一個詞由多個詞組成的題,是拿dp或者dfs來解,dp本質上其實也是dfs。這道題要判斷輸入的詞能否由字典里的單詞組成,那么可以用個boolean的dp數組。
initialize dp[s.length() + 1], dp[0] = true
dp function: dp[i] = dp[j] & (s[j, i] in dict)
result: dp[s.length()]
第二步的dp function,兩種找的方法,一個是j從0到i - 1循環,還有一種是traverse整個dict,j = i - word.length()。當字典很大,s不長的時候,用第一種,當字典不大,但是s很長的時候用第二種。這題現在給的dict是個list不是set沒法O(1)判斷s[j, i] in dict,所以用第二種來寫。
public class Solution { public boolean wordBreak(String s, ListWord Break IIwordDict) { /* boolean dp[s.length() + 1] * 1. initial: dp[0] = true * 2. function: dp[i] = dp[j] & (s[j, i] in dict) * 3. result: dp[s.length()] */ boolean[] dp = new boolean[s.length() + 1]; dp[0] = true; for(int i = 1; i < dp.length; i++) { for(String word : wordDict) { int j = i - word.length(); if(j >= 0 && dp[j] && s.substring(j, i).equals(word)) { dp[i] = true; break; } } } return dp[s.length()]; } }
鏈接:https://leetcode.com/problems...
和上一題不同的是,這道題要返回所有可能的組合。所以現在dp[i]里面應該存可以使長度為i所有可能的String里的最后一個word。dp有兩種寫法,一個就是直接寫成數組:List[]的形式,不能形成的dp[i] = null。還有一個是用個hashmap:Map
dp結束之后,第二步就是通過dp里面保存的word,一步一步回溯找到所有結果。
public class Solution { public ListwordBreak(String s, List wordDict) { /* dp: * map > dp * dp function: put(i, word) if s[j, i] = word & j is a key of dp * result: dp[s.length()] backtracking */ dp.put(0, new ArrayList()); dp.get(0).add(""); for(int i = 1; i < s.length() + 1; i++) { for(String word : wordDict) { int j = i - word.length(); if(j >= 0 && s.substring(j, i).equals(word) && dp.containsKey(j)) { if(!dp.containsKey(i)) dp.put(i, new ArrayList()); dp.get(i).add(word); } } } List result = new ArrayList(); if(!dp.containsKey(s.length())) return result; // backtracking dfs(result, s.length(), ""); return result; } Map > dp = new HashMap(); private void dfs(List result, int pos, String cur) { // base case if(pos == 0) { result.add(cur); return; } for(String word : dp.get(pos)) { int j = pos - word.length(); if(j >= 0 && dp.containsKey(j)) { dfs(result, j, word + (cur.equals("") ? "" : " " + cur)); } } } }
dp本質上就是dfs,這題可以dfs來做。直接的dfs會超時,考慮記憶化搜索。兩種方式:一個是用dp[i]來記錄(i,n)有valid的string,參考這個人的博客:
http://www.cnblogs.com/grandy...
public class Solution { public ListwordBreak(String s, List wordDict) { List result = new ArrayList(); dp = new boolean[s.length() + 1]; Arrays.fill(dp, true); // backtracking dfs(result, 0, "", s, wordDict); return result; } boolean[] dp; private void dfs(List result, int pos, String cur, String s, List wordDict) { // base case if(pos == s.length()) { result.add(cur); return; } if(!dp[pos]) return; for(String word : wordDict) { int i = pos + word.length(); if(i <= s.length() && s.substring(pos, i).equals(word)) { int size = result.size(); dfs(result, i, (cur.equals("") ? "" : cur + " ") + word, s, wordDict); if(size == result.size()) dp[i] = false; } } } }
還有一種,直接拿hashmap記錄走過的路,這樣就不會重復搜索了,和dp其實是一樣的,但是這里把整個路徑都保存了,之后就不需要再backtracking找路徑了,參考discussion里面給的:
public class Solution { public ListwordBreak(String s, List wordDict) { // backtracking return dfs(s, wordDict); } Map > map = new HashMap(); private List dfs(String s, List wordDict) { if(map.containsKey(s)) return map.get(s); // bottom up List result = new ArrayList(); if(s.length() == 0) { result.add(""); return result; } for(String word : wordDict) { int i = word.length(); if(i <= s.length() && s.substring(0, i).equals(word)) { List subs = dfs(s.substring(i), wordDict); for(String sub : subs) { result.add(word + (sub.equals("") ? "" : " " + sub)); } } } map.put(s, result); return result; } }
這種記憶化dfs的寫法原理和path sum的有點像。
Concatenated Words鏈接:https://leetcode.com/problems...
這道題可以用dp的方法,和word break一樣,多加個循環,復雜度是O(N^3),這道題注意下,字典比較大,用第二種來寫dp function會超時,只能用第一種。
public class Solution { public ListfindAllConcatenatedWordsInADict(String[] words) { List result = new ArrayList(); Set set = new HashSet(Arrays.asList(words)); for(String word : words) { set.remove(word); if(wordBreak(set, word)) result.add(word); set.add(word); } return result; } private boolean wordBreak(Set words, String s) { if(s == null || s.length() == 0) return false; boolean[] dp = new boolean[s.length() + 1]; dp[0] = true; for(int i = 1; i < dp.length; i++) { for(int j = i-1; j >= 0; j--) { if(dp[j] && words.contains(s.substring(j, i))) { dp[i] = true; break; } } } return dp[s.length()]; } }
看了discussion里面的優化,感覺很好,思路是一個word要想被其他詞組成,其他詞的長度必然是<這個詞的。所以事先對words排序。這個lc里面一開始沒加“word.length() > 1”的條件,測試里面會出現一個字母的結果,很神奇啊,到現在也不知道錯在哪。。
public class Solution { public ListfindAllConcatenatedWordsInADict(String[] words) { List result = new ArrayList(); Arrays.sort(words, (a, b) -> a.length() - b.length()); Set set = new HashSet(); for(String word : words) { if(word.length() > 1 && wordBreak(set, word)) result.add(word); set.add(word); } return result; } private boolean wordBreak(Set set, String s) { if(s == null || s.length() == 0 || set.isEmpty()) return false; boolean[] dp = new boolean[s.length() + 1]; dp[0] = true; for(int i = 1; i < dp.length; i++) { for(int j = i-1; j >= 0; j--) { if(dp[j] && set.contains(s.substring(j, i))) { dp[i] = true; break; } } } return dp[s.length()]; } }
不用set保存word,用trie tree一個一個往里加word和查找,其他都和前一種方法一樣。
public class Solution { public ListfindAllConcatenatedWordsInADict(String[] words) { tree = new Trie(); List result = new ArrayList(); Arrays.sort(words, (a, b) -> a.length() - b.length()); for(String word : words) { if(word.length() > 1 && dfs(word)) result.add(word); tree.addWord(word); } return result; } Trie tree; private boolean dfs(String s) { if(s.length() == 0) return true; for(int i = 1; i <= s.length(); i++) { if(tree.search(s.substring(0, i))) { if(dfs(s.substring(i))) return true; } } return false; } class TrieNode { TrieNode[] children = new TrieNode[26]; boolean isWord; } class Trie { TrieNode root; private int getIndex(char c) { return c - "a"; } public Trie() { root = new TrieNode(); } public Trie(String[] words) { root = new TrieNode(); for(String word : words) addWord(word); } public void addWord(String word) { TrieNode node = root; for(int i = 0; i < word.length(); i++) { if(node.children[getIndex(word.charAt(i))] == null) node.children[getIndex(word.charAt(i))] = new TrieNode(); node = node.children[getIndex(word.charAt(i))]; } node.isWord = true; } public boolean search(String word) { TrieNode node = root; for(int i = 0; i < word.length(); i++) { if(node.children[getIndex(word.charAt(i))] == null) return false; node = node.children[getIndex(word.charAt(i))]; } return node.isWord; } } }
直接用trie tree, 沒有優化,結果stackoverflow了。。
public class Solution { public ListfindAllConcatenatedWordsInADict(String[] words) { tree = new Trie(words); List result = new ArrayList(); for(String word : words) { if(word.length() > 1 && dfs(word, 0)) result.add(word); } return result; } Trie tree; private boolean dfs(String s, int pos) { if(s.length() == pos) return true; for(int i = pos; i <= s.length(); i++) { if(pos == 0 && i == s.length()) return false; if(tree.search(s.substring(pos, i))) { if(dfs(s, i)) return true; } } return false; } class TrieNode { TrieNode[] children = new TrieNode[26]; boolean isWord; } class Trie { TrieNode root; private int getIndex(char c) { return c - "a"; } public Trie() { root = new TrieNode(); } public Trie(String[] words) { root = new TrieNode(); for(String word : words) addWord(word); } public void addWord(String word) { TrieNode node = root; for(int i = 0; i < word.length(); i++) { if(node.children[getIndex(word.charAt(i))] == null) node.children[getIndex(word.charAt(i))] = new TrieNode(); node = node.children[getIndex(word.charAt(i))]; } node.isWord = true; } public boolean search(String word) { TrieNode node = root; for(int i = 0; i < word.length(); i++) { if(node.children[getIndex(word.charAt(i))] == null) return false; node = node.children[getIndex(word.charAt(i))]; } return node.isWord; } } }
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/66575.html
摘要:復雜度時間空間為長度,為大小空間復雜度是是因為我用存信息,只動態地存當前的路徑如果用來存信息的話空間復雜度就是時間復雜度對每個點都要作為起始點,對于每個起始點,拓展一次有四個可能性四個鄰居,要拓展次長度為。思路暴力搜索帶走。 Word Search I Given a 2D board and a word, find if the word exists in the grid. ...
摘要:題目要求相比于,要求返回所有的最短路徑。至于如何生成該有向圖,則需要通過廣度優先算法,利用隊列來實現。將每一層的分別入棧。如果遇到則至該層結尾廣度優先算法結束。通過這種方式來防止形成圈。 題目要求 Given two words (beginWord and endWord), and a dictionarys word list, find all shortest transfo...
摘要:存放過程中的所有集合為所有的結尾,則順序存放這個結尾對應的中的所有存放同一個循環的新加入的,在下一個循環再依次對其中元素進行進一步的把首個字符串放入新,再將放入,并將鍵值對放入,進行初始化 Problem Given two words (start and end), and a dictionary, find all shortest transformation sequenc...
摘要:題目要求現在有一個非空字符串和一個非空的字典?,F在向中添加空格從而構成一個句子,其中這個句子的所有單詞都存在與中。 題目要求 Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaces in s to construct a sentence ...
摘要:所以只要驗證滿足這個條件,我們則可以確定這個較長的字符串也是可分解的。同時,我們用數組記錄下字符串長度遞增時可分解的情況,以供之后使用,避免重復計算。當遍歷完這個詞典并找出所有以第一個字母開頭的詞以后,我們進入下一輪搜索。 Word Break I Given a string s and a dictionary of words dict, determine if s can ...
閱讀 3190·2021-11-10 11:35
閱讀 1295·2019-08-30 13:20
閱讀 1117·2019-08-29 16:18
閱讀 2131·2019-08-26 13:54
閱讀 2155·2019-08-26 13:50
閱讀 955·2019-08-26 13:39
閱讀 2473·2019-08-26 12:08
閱讀 1951·2019-08-26 10:37