关于我的 Leetcode 题目解答，代码前往 Github：https://github.com/chenxiangcyr/leetcode-answers
Word Square题目
LeetCode题目：422. Valid Word Square
Given a sequence of words, check whether it forms a valid word square.
A sequence of words forms a valid word square if the kth row and column read the exact same string, where 0 ≤ k < max(numRows, numColumns).
Note:
The number of words given is at least 1 and does not exceed 500.
Word length will be at least 1 and does not exceed 500.
Each word contains only lowercase English alphabet a-z.
Example 1:
Input:
[
"abcd",
"bnrt",
"crmy",
"dtye"
]
Output:
true
Explanation:
The first row and first column both read "abcd".
The second row and second column both read "bnrt".
The third row and third column both read "crmy".
The fourth row and fourth column both read "dtye".
Therefore, it is a valid word square.
class Solution {
public boolean validWordSquare(List<String> words) {
if(words == null || words.size() == 0) return true;
// 遍历所有行
for(int i = 0; i < words.size(); i++) {
// 遍历第i列
for(int j = 0; j < words.get(i).length(); j++){
if(j >= words.size() || words.get(j).length() <= i || words.get(j).charAt(i) != words.get(i).charAt(j)) {
return false;
}
}
}
return true;
}
}
LeetCode题目：425. Word Squares
Given a set of words (without duplicates), find all word squares you can build from them.
A sequence of words forms a valid word square if the kth row and column read the exact same string, where 0 ≤ k < max(numRows, numColumns).
For example, the word sequence ["ball","area","lead","lady"] forms a word square because each word reads the same both horizontally and vertically.
b a l l
a r e a
l e a d
l a d y
Note:
- There are at least 1 and at most 1000 words.
- All words will have the exact same length.
- Word length is at least 1 and at most 5.
- Each word contains only lowercase English alphabet
a-z.
class Solution {
class TrieNode {
List<String> startWith;
TrieNode[] children;
TrieNode() {
startWith = new ArrayList<>();
children = new TrieNode[26];
}
}
class Trie {
TrieNode root;
Trie(String[] words) {
root = new TrieNode();
for (String w : words) {
TrieNode cur = root;
for (char ch : w.toCharArray()) {
int idx = ch - 'a';
if (cur.children[idx] == null)
cur.children[idx] = new TrieNode();
cur.children[idx].startWith.add(w);
cur = cur.children[idx];
}
}
}
List<String> findByPrefix(String prefix) {
List<String> ans = new ArrayList<>();
TrieNode cur = root;
for (char ch : prefix.toCharArray()) {
int idx = ch - 'a';
if (cur.children[idx] == null)
return ans;
cur = cur.children[idx];
}
ans.addAll(cur.startWith);
return ans;
}
}
List<List<String>> ans = new ArrayList<>();
List<String> ansBuilder = new ArrayList<>();
public List<List<String>> wordSquares(String[] words) {
if (words == null || words.length == 0)
return ans;
// 构造Trie树
Trie trie = new Trie(words);
int len = words[0].length();
// 遍历每一个word，都有可能成为第一条
for (String w : words) {
ansBuilder = new ArrayList<>();
ansBuilder.add(w);
search(len, trie);
}
return ans;
}
private void search(int len, Trie tr) {
if (ansBuilder.size() == len) {
ans.add(new ArrayList<>(ansBuilder));
}
else {
int idx = ansBuilder.size();
StringBuilder prefixBuilder = new StringBuilder();
for (String s : ansBuilder)
prefixBuilder.append(s.charAt(idx));
// 找到所有备选words
List<String> startWith = tr.findByPrefix(prefixBuilder.toString());
for (String sw : startWith) {
ansBuilder.add(sw);
search(len, tr);
// backtracking 回溯
ansBuilder.remove(ansBuilder.size() - 1);
}
}
}
}
Word Search题目
LeetCode题目：79. Word Search
Given a 2D board and a word, find if the word exists in the grid.
The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.
For example,
Given board =
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]
word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.
class Solution {
public boolean exist(char[][] board, String word) {
if(board == null || board.length == 0 || board[0].length == 0) return false;
if(word.isEmpty()) return true;
int rows = board.length;
int columns = board[0].length;
char[] wordArr = word.toCharArray();
for(int i = 0; i < rows; i++) {
for(int j = 0; j < columns; j++) {
if(board[i][j] == wordArr[0]) {
if(dfs(board, wordArr, i, j, rows, columns, 0)) return true;
}
}
}
return false;
}
public boolean dfs(char[][] board, char[] wordArr, int i, int j, int rows, int columns, int curWordIdx) {
// 通过操作board，避免使用额外空间存储 visited 信息
char temp = board[i][j];
board[i][j] = '0';
if(curWordIdx == wordArr.length - 1) {
return true;
}
int[][] dir = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
boolean found = false;
for(int[] d : dir) {
int ni = i + d[0];
int nj = j + d[1];
if(ni >= 0 && ni < rows && nj >= 0 && nj < columns && board[ni][nj] == wordArr[curWordIdx + 1]) {
found = found || dfs(board, wordArr, ni, nj, rows, columns, curWordIdx + 1);
}
}
// backtacking
board[i][j] = temp;
return found;
}
}
LeetCode题目：212. Word Search II
Given a 2D board and a list of words from the dictionary, find all words in the board.
Each word must be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.
For example,
Given words = ["oath","pea","eat","rain"] and board =
[
['o','a','a','n']
['e','t','a','e']
['i','h','k','r']
['i','f','l','v']
]
Return ["eat","oath"].
Note:
You may assume that all inputs are consist of lowercase letters a-z.
思路参见 https://leetcode.com/problems/word-search-ii/discuss/59780/Java-15ms-Easiest-Solution-(100.00)
class Solution {
public List<String> findWords(char[][] board, String[] words) {
List<String> res = new ArrayList<>();
// 构造Trie树
TrieNode root = buildTrie(words);
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
dfs (board, i, j, root, res);
}
}
return res;
}
public void dfs(char[][] board, int i, int j, TrieNode p, List<String> res) {
char c = board[i][j];
// 已经访问过，或者不存在该字符
if (c == '#' || p.next[c - 'a'] == null) return;
p = p.next[c - 'a'];
if (p.word != null) { // found one
res.add(p.word);
p.word = null; // de-duplicate
}
board[i][j] = '#';
if (i > 0) dfs(board, i - 1, j ,p, res);
if (j > 0) dfs(board, i, j - 1, p, res);
if (i < board.length - 1) dfs(board, i + 1, j, p, res);
if (j < board[0].length - 1) dfs(board, i, j + 1, p, res);
// backtracking
board[i][j] = c;
}
public TrieNode buildTrie(String[] words) {
TrieNode root = new TrieNode();
for (String w : words) {
TrieNode p = root;
for (char c : w.toCharArray()) {
int i = c - 'a';
if (p.next[i] == null) {
p.next[i] = new TrieNode();
}
p = p.next[i];
}
p.word = w;
}
return root;
}
class TrieNode {
TrieNode[] next = new TrieNode[26];
String word;
}
}
Word Break题目
LeetCode题目：139. Word Break
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".
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
return wordBreakIterative(s, wordDict);
}
// DP Iterative
public boolean wordBreakIterative(String s, List<String> wordDict) {
if(s == null || s.length() == 0) return false;
// isValid[i] contains true/false when visiting element i
boolean[] isValid = new boolean[s.length()];
Arrays.fill(isValid, false);
// init
isValid[0] = wordDict.contains(s.substring(0, 1));
for(int i = 1; i < s.length(); i++) {
for(int j = i; j >=0; j--) {
String subString = s.substring(j, i + 1);
if(wordDict.contains(subString)) {
if(j == 0 || isValid[j - 1])
isValid[i] = true;
}
}
}
return isValid[isValid.length - 1];
}
// DP Recursive: Time Limit Exceeded
public boolean wordBreakRecursive(String s, List<String> wordDict, int startIdx) {
if(startIdx >= s.length()) {
return true;
}
for(int i = startIdx + 1; i <= s.length(); i++) {
String subString = s.substring(startIdx, i);
if(wordDict.contains(subString)) {
if(wordBreakRecursive(s, wordDict, i)) {
return true;
}
}
}
return false;
}
}
LeetCode题目：140. Word Break II
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 where each word is a valid dictionary word. You may assume the dictionary does not contain duplicate words.
Return all such possible sentences.
For example, given
s = "catsanddog",
dict = ["cat", "cats", "and", "sand", "dog"].
A solution is ["cats and dog", "cat sand dog"].
public class Solution {
public List<String> wordBreak(String s, List<String> wordDict) {
// dp[i] 存储的是位置i之前所有可能的字符串
LinkedList<String>[] dp = new LinkedList[s.length() + 1];
LinkedList<String> initial = new LinkedList<>();
initial.add("");
dp[0] = initial;
for (int i = 1; i <= s.length(); i++) {
LinkedList<String> list = new LinkedList<>();
for (int j = 0; j < i; j++) {
// dp[j].size() > 0表示位置j是合理的
if (dp[j].size() > 0 && wordDict.contains(s.substring(j, i))) {
for (String l : dp[j]) {
list.add(l + (l.equals("") ? "" : " ") + s.substring(j, i));
}
}
}
dp[i] = list;
}
return dp[s.length()];
}
}
Word Ladder题目
LeetCode题目：127. Word Ladder
Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence from beginWord to endWord, such that:
- Only one letter can be changed at a time.
- Each transformed word must exist in the word list. Note that beginWord is not a transformed word.
For example,
Given:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log","cog"]
As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.
Note:
- Return 0 if there is no such transformation sequence.
- All words have the same length.
- All words contain only lowercase alphabetic characters.
- You may assume no duplicates in the word list.
- You may assume beginWord and endWord are non-empty and are not the same.
class Solution {
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
// BFS 广度优先搜索
Set<String> reached = new HashSet<String>();
// 第一层的单词列表
int distance = 1;
reached.add(beginWord);
while (!reached.contains(endWord)) {
Set<String> toAdd = new HashSet<String>();
for (String each : reached) {
for (int i = 0; i < each.length(); i++) {
// 每次更改一个字符，找到只相差一个字符的所有word
char[] chars = each.toCharArray();
for (char ch = 'a'; ch <= 'z'; ch++) {
chars[i] = ch;
String word = new String(chars);
if (wordList.contains(word)) {
toAdd.add(word);
// 删除，起到了标记visited作用
wordList.remove(word);
}
}
}
}
// 新的一层
distance++;
// 没有更多的word了
if (toAdd.size() == 0) return 0;
reached = toAdd;
}
return distance;
}
}
LeetCode题目：126. Word Ladder II
Given two words (beginWord and endWord), and a dictionary's word list, find all shortest transformation sequence(s) from beginWord to endWord, such that:
- Only one letter can be changed at a time
- Each transformed word must exist in the word list. Note that beginWord is not a transformed word.
For example,
Given:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log","cog"]
Return
[
["hit","hot","dot","dog","cog"],
["hit","hot","lot","log","cog"]
]
Note:
- Return an empty list if there is no such transformation sequence.
- All words have the same length.
- All words contain only lowercase alphabetic characters.
- You may assume no duplicates in the word list.
- You may assume beginWord and endWord are non-empty and are not the same.
class Solution {
public List<List<String>> findLadders(String start, String end, List<String> wordList) {
HashSet<String> dict = new HashSet<String>(wordList);
List<List<String>> res = new ArrayList<List<String>>();
HashMap<String, ArrayList<String>> nodeNeighbors = new HashMap<String, ArrayList<String>>();// Neighbors for every node
HashMap<String, Integer> distance = new HashMap<String, Integer>();// Distance of every node from the start node
ArrayList<String> solution = new ArrayList<String>();
dict.add(start);
bfs(start, end, dict, nodeNeighbors, distance);
dfs(start, end, dict, nodeNeighbors, distance, solution, res);
return res;
}
// BFS: Trace every node's distance from the start node (level by level).
private void bfs(String start, String end, Set<String> dict, HashMap<String, ArrayList<String>> nodeNeighbors, HashMap<String, Integer> distance) {
for (String str : dict) {
nodeNeighbors.put(str, new ArrayList<String>());
}
Queue<String> queue = new LinkedList<String>();
queue.offer(start);
distance.put(start, 0);
while (!queue.isEmpty()) {
int count = queue.size();
boolean foundEnd = false;
for (int i = 0; i < count; i++) {
String cur = queue.poll();
int curDistance = distance.get(cur);
ArrayList<String> neighbors = getNeighbors(cur, dict);
for (String neighbor : neighbors) {
nodeNeighbors.get(cur).add(neighbor);
if (!distance.containsKey(neighbor)) {// Check if visited
distance.put(neighbor, curDistance + 1);
if (end.equals(neighbor))// Found the shortest path
foundEnd = true;
else
queue.offer(neighbor);
}
}
}
if (foundEnd)
break;
}
}
// Find all next level nodes.
private ArrayList<String> getNeighbors(String node, Set<String> dict) {
ArrayList<String> res = new ArrayList<String>();
char chs[] = node.toCharArray();
for (char ch ='a'; ch <= 'z'; ch++) {
for (int i = 0; i < chs.length; i++) {
if (chs[i] == ch) continue;
char old_ch = chs[i];
chs[i] = ch;
if (dict.contains(String.valueOf(chs))) {
res.add(String.valueOf(chs));
}
chs[i] = old_ch;
}
}
return res;
}
// DFS: output all paths with the shortest distance.
private void dfs(String cur, String end, Set<String> dict, HashMap<String, ArrayList<String>> nodeNeighbors, HashMap<String, Integer> distance, ArrayList<String> solution, List<List<String>> res) {
solution.add(cur);
if (end.equals(cur)) {
res.add(new ArrayList<String>(solution));
}
else {
for (String next : nodeNeighbors.get(cur)) {
if (distance.get(next) == distance.get(cur) + 1) {
dfs(next, end, dict, nodeNeighbors, distance, solution, res);
}
}
}
// backtracking
solution.remove(solution.size() - 1);
}
}
