写这篇文章是因为word break和word search都很经典。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，其实这个值怎么赋值在写状态转移方程的时候能体现出来。
状态转移方程：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，为最终状态
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];
// 遍历整个二维数组，用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;
// 边界以及是否已经访问判断
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”这样的单词得继续回溯
}
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;
}
}
网友评论