寫這篇文章是因為word break和word search都很經(jīng)典。word search ii 還涉及到Trie。
Word Break
題目
給字符串s嘿辟，字典wordDict冒萄，判斷s能否用wordDict里的字符串組成。
例子
Input: s = "leetcode", wordDict = ["leet", "code"]
Output: true
Explanation: "leetcode" = "leet code".
方法
使用DP荔泳。dp[i]表示s.substring(0,i)是有效的蕉饼。i最多能取到s.length()，所以dp[] = new int[s.length() + 1]玛歌。
初始值dp[0] = true昧港，其實這個值怎么賦值在寫狀態(tài)轉(zhuǎn)移方程的時候能體現(xiàn)出來。
狀態(tài)轉(zhuǎn)移方程：dp[i] = dp[j] && wordDict.has(s.substring(j, i))支子。而j的取值范圍是[0,i)创肥。
代碼
public boolean wordBreak(String s, List<String> wordDict) {
boolean[] f = new boolean[s.length() + 1]; // 從[0,i)是valid
f[0] = true;
for (int i = 1; i <= s.length(); i++) {
// [0,i]能否被組成 取決于是否存在j，使得[0,j]true&substring[i,j]存在于dict中
for (int j = 0; j < i; j++) {
if (f[j] && wordDict.contains(s.substring(j, i))) {
f[i] = true; // f[s.length()] => [0,len)
break; // 退出里面的那個for loop
}
}
}
return f[s.length()];
}
復雜度
時間復雜度：O(n^2)
空間復雜度：O(n)
Word Break II
題目
給字符串s，字典wordDict叹侄，返回所有組合方式巩搏。
例子
Input: s = "catsanddog", wordDict = ["cat", "cats", "and", "sand", "dog"]
Output:
[
"cats and dog",
"cat sand dog"
]
方法
使用DFS，但是使用一個memo table去記錄遇到并計算完的substring趾代。
為什么想到DFS：因為讓我們列出所有的解塔猾，一般列所有就需要窮舉，就是每種情況都找到稽坤。
代碼
class Solution {
// 使用了memo table丈甸，可以變成dp問題
// <任意的substring，這個substring可以用什么來組成>
Map<String,List<String>> map = new HashMap<>();
public List<String> wordBreak(String s, List<String> wordDict) {
return dfs(s, new HashSet<>(wordDict));
}
// DFS 返回一個 list 包含從s中提取的所有substring
// s的長度不斷縮小尿褪，知道為empty list睦擂，為最終狀態(tài)
private List<String> dfs(String s, Set<String> wordDict) {
if (map.containsKey(s)) {
return map.get(s);
}
LinkedList<String> res = new LinkedList<String>();
if (s.length() == 0) {
res.add("");
return res;
}
for (String word : wordDict) {
if (s.startsWith(word)) {
List<String> sublist = dfs(s.substring(word.length()), wordDict);
for (String sub : sublist) {
res.add(word + (sub.isEmpty() ? "" : " ") + sub);
}
}
}
map.put(s, res);
return res;
}
}
Word Search
題目
給字符串word，看能不能搜到杖玲。
例子
board =
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]
Given word = "ABCCED", return true.
Given word = "SEE", return true.
Given word = "ABCB", return false.
方法
使用DFS顿仇。
代碼
public class Solution {
public boolean exist(char[][] board, String word) {
if (board == null || board.length == 0 || word == null || word.length() == 0) {
return false;
}
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
if (board[i][j] == word.charAt(0)) {
if (judge(board, i, j, word, 0)) {
return true;
}
}
}
}
return false;
}
public boolean judge(char[][] board, int index1, int index2, String s, int indexS) {
if (indexS >= s.length()) {
return true;
}
if (index1 < 0 || index1 >= board.length || index2 < 0 || index2 >= board[0].length) {
return false;
}
if (s.charAt(indexS) == board[index1][index2]) {
char tmp = board[index1][index2]; // 類似visited
board[index1][index2] = '*';
if (judge(board, index1 + 1, index2, s, indexS + 1)
|| judge(board, index1 - 1, index2, s, indexS + 1)
|| judge(board, index1, index2 + 1, s, indexS + 1)
|| judge(board, index1, index2 - 1, s, indexS + 1)) {
return true;
}
board[index1][index2] = tmp;
}
return false;
}
}
Word Search II
題目
給一堆字符串word，返回所有能搜到的字符串摆马。
例子
Input:
board = [
['o','a','a','n'],
['e','t','a','e'],
['i','h','k','r'],
['i','f','l','v']
]
words = ["oath","pea","eat","rain"]
Output: ["eat","oath"]
方法
使用DFS+Trie臼闻。
代碼
class Solution {
// 字典樹結點
class TrieNode {
public String val;
public TrieNode[] child = new TrieNode[26];
public boolean isLeaf = false;
TrieNode(String val) {
this.val = val;
}
}
// 字典樹
class Trie {
public TrieNode root;
Trie(TrieNode root) {
this.root = root;
}
public void insert(String s) {
TrieNode cur = root;
for (char c : s.toCharArray()) {
if (cur.child[c-'a'] == null) {
cur.child [c-'a'] = new TrieNode("");
cur = cur.child[c-'a'];
} else {
cur = cur.child [c-'a'];
}
}
cur.isLeaf = true;
cur.val = s;
}
}
public List<String> findWords(char[][] board, String[] words) {
// 構建字典樹
TrieNode root = new TrieNode("");
Trie myTrie = new Trie(root);
for (String s:words) {
myTrie.insert(s);
}
// 使用set防止重復
Set<String> result = new HashSet<>();
int m = board.length;
int n = board[0].length;
boolean[][] visited = new boolean[m][n];
// 遍歷整個二維數(shù)組，用DFS來遍歷所有可能存在在Trie里的排列組合
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
find(board, visited, i, j, result, root);
}
}
return new LinkedList<String>(result);
}
private void find(char[][] board, boolean[][] visited,
int i, int j, Set<String> result, TrieNode cur) {
int m = board.length;
int n = board[0].length;
// 邊界以及是否已經(jīng)訪問判斷
if (i < 0 || i >= m || j < 0 || j >= n || visited[i][j]) {
return;
}
cur = cur.child[board[i][j]-'a'];
visited[i][j] = true;
if (cur == null) {
visited[i][j] = false; // 如果單詞不匹配囤采，回退
return;
}
if (cur.isLeaf) { // 找到單詞加入
result.add(cur.val); // 找到單詞后不能回退述呐，因為可能是“ad” “addd”這樣的單詞得繼續(xù)回溯
}
find(board, visited, i + 1, j, result, cur);
find(board, visited, i, j + 1, result, cur);
find(board, visited, i, j - 1, result, cur);
find(board, visited, i - 1, j, result, cur);
// 最后要回退，因為下一個起點可能會用到上一個起點的字符
visited[i][j]=false;
}
}
