zzzrf:给出一个由小写字母组成的矩阵和一个字典。找出所有同时在字典和矩阵中出现的单词。一个单词可以从矩阵中的任意位置开始,可以向左 /右 /上 /下四个相邻方向移动。一个字母在一个单词中只能被使用一次。且字典中不存在重复单词。
在线做题地址
样例 1:
输入:["doaf","agai","dcan"],["dog","dad","dgdg","can","again"]
输出:["again","can","dad","dog"]
解释:
d o a f
a g a i
d c a n
矩阵中查找,返回 ["again","can","dad","dog"]。
样例 2:
输入:["a"],["b"]
输出:[]
解释:
a
矩阵中查找,返回 []。
题解
使用 HashMap 的版本。 将所有的单词的 Prefix 都加入 HashMap 中。HashMap 的 value 用户判断这是一个 prefix 还是一个 word 。 如果是 prefix 就是 false,如果是 word 就是 true.
public class Solution {
public static int[] dx = {0, 1, -1, 0};
public static int[] dy = {1, 0, 0, -1};
/** * @param board: A list of lists of character * @param words: A list of string * @return: A list of string */
public List<String> wordSearchII(char[][] board, List<String> words) {
if (board == null || board.length == 0) {
return new ArrayList<>();
}
if (board[0] == null || board[0].length == 0) {
return new ArrayList<>();
}
boolean[][] visited = new boolean[board.length][board[0].length];
Map<String, Boolean> prefixIsWord = getPrefixSet(words);
Set<String> wordSet = new HashSet<>();
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[i].length; j++) {
visited[i][j] = true;
dfs(board, visited, i, j, String.valueOf(board[i][j]), prefixIsWord, wordSet);
visited[i][j] = false;
}
}
return new ArrayList<String>(wordSet);
}
private Map<String, Boolean> getPrefixSet(List<String> words) {
Map<String, Boolean> prefixIsWord = new HashMap<>();
for (String word : words) {
for (int i = 0; i < word.length() - 1; i++) {
String prefix = word.substring(0, i + 1);
if (!prefixIsWord.containsKey(prefix)) {
prefixIsWord.put(prefix, false);
}
}
prefixIsWord.put(word, true);
}
return prefixIsWord;
}
private void dfs(char[][] board,
boolean[][] visited,
int x,
int y,
String word,
Map<String, Boolean> prefixIsWord,
Set<String> wordSet) {
if (!prefixIsWord.containsKey(word)) {
return;
}
if (prefixIsWord.get(word)) {
wordSet.add(word);
}
for (int i = 0; i < 4; i++) {
int adjX = x + dx[i];
int adjY = y + dy[i];
if (!inside(board, adjX, adjY) || visited[adjX][adjY]) {
continue;
}
visited[adjX][adjY] = true;
dfs(board, visited, adjX, adjY, word + board[adjX][adjY], prefixIsWord, wordSet);
visited[adjX][adjY] = false;
}
}
private boolean inside(char[][] board, int x, int y) {
return x >= 0 && x < board.length && y >= 0 && y < board[0].length;
}
}
Google Chrome Helper 问题fox:macbook 疯狂风扇旋转,cpu100,一看是 Google Chrome Helper 占了 99 的 cpu,沙掉就好了。 这个问题几天内发生了两次了,查了一下似乎是一个历史遗留问题。 都 2020 年了,为啥还没修复这个问题。
谷歌云(Google Cloud)免费政策改变了?只有三个月了吗?jememouse:https://cloud.google.com/free/docs/gcp-free-tier?hl=zh-cn 有没有朋友最近新建过,是否只有三个月了?Tink:是的 gqbre:握草。。 白嫖的日子一去不复返 trepwq:是…
Google 面试题:岛屿的个数 IIzzzrf:给定 n, m, 分别代表一个二维矩阵的行数和列数, 并给定一个大小为 k 的二元数组 A. 初始二维矩阵全 0. 二元数组 A 内的 k 个元素代表 k 次操作, 设第 i 个元素为 (A[i].x, A[i].y), 表示把二维矩阵中下标为 A[i].x 行 A[i].y 列的元素由海洋变为岛屿. 问在每次操作之后, 二维矩阵中岛屿的数量. …
Google 的磁悬浮负载均衡器holinhot:https://research.google/pubs/pub44824/ 想试一试这个磁悬浮负载均衡器, 文档我看了,说得很牛逼的样子,但是我找了很久没找到在哪下载啊。 难道不是开源的,只是出来水一下让大家看吗?holinhot:https://opensource.google/projects/list/featured 在这也没找…
一个 Google Drive 搜索引擎xinyana:https://zhao.pp.ua 一个基于ElasticSearch的 Google Drive 搜索引擎,可搜索、可直接下载