{"id":159874,"date":"2020-09-24T14:54:55","date_gmt":"2020-09-24T06:54:55","guid":{"rendered":"http:\/\/4563.org\/?p=159874"},"modified":"2020-09-24T14:54:55","modified_gmt":"2020-09-24T06:54:55","slug":"google-%e9%9d%a2%e8%af%95%e9%a2%98%ef%bc%9a%e5%8d%95%e8%af%8d%e6%90%9c%e7%b4%a2-ii","status":"publish","type":"post","link":"http:\/\/4563.org\/?p=159874","title":{"rendered":"Google \u9762\u8bd5\u9898\uff1a\u5355\u8bcd\u641c\u7d22 II"},"content":{"rendered":"
\n
\n
\n

Google \u9762\u8bd5\u9898\uff1a\u5355\u8bcd\u641c\u7d22 II <\/h1>\n

<\/p>\n

\n
\u8cc7\u6df1\u5927\u4f6c : zzzrf <\/span> <\/i> 1<\/span> <\/div>\n
<\/div>\n<\/p><\/div>\n<\/p><\/div>\n<\/p><\/div>\n
<\/p>\n

\u7ed9\u51fa\u4e00\u4e2a\u7531\u5c0f\u5199\u5b57\u6bcd\u7ec4\u6210\u7684\u77e9\u9635\u548c\u4e00\u4e2a\u5b57\u5178\u3002\u627e\u51fa\u6240\u6709\u540c\u65f6\u5728\u5b57\u5178\u548c\u77e9\u9635\u4e2d\u51fa\u73b0\u7684\u5355\u8bcd\u3002\u4e00\u4e2a\u5355\u8bcd\u53ef\u4ee5\u4ece\u77e9\u9635\u4e2d\u7684\u4efb\u610f\u4f4d\u7f6e\u5f00\u59cb\uff0c\u53ef\u4ee5\u5411\u5de6 \/\u53f3 \/\u4e0a \/\u4e0b\u56db\u4e2a\u76f8\u90bb\u65b9\u5411\u79fb\u52a8\u3002\u4e00\u4e2a\u5b57\u6bcd\u5728\u4e00\u4e2a\u5355\u8bcd\u4e2d\u53ea\u80fd\u88ab\u4f7f\u7528\u4e00\u6b21\u3002\u4e14\u5b57\u5178\u4e2d\u4e0d\u5b58\u5728\u91cd\u590d\u5355\u8bcd\u3002<\/p>\n

\u5728\u7ebf\u505a\u9898\u5730\u5740<\/p>\n

\u6837\u4f8b 1:<\/h2>\n
\u8f93\u5165\uff1a[\"doaf\",\"agai\",\"dcan\"]\uff0c[\"dog\",\"dad\",\"dgdg\",\"can\",\"again\"] \u8f93\u51fa\uff1a[\"again\",\"can\",\"dad\",\"dog\"] \u89e3\u91ca\uff1a   d o a f   a g a i   d c a n \u77e9\u9635\u4e2d\u67e5\u627e\uff0c\u8fd4\u56de [\"again\",\"can\",\"dad\",\"dog\"]\u3002 <\/code><\/pre>\n
\u6837\u4f8b 2:<\/h2>\n
\u8f93\u5165\uff1a[\"a\"]\uff0c[\"b\"] \u8f93\u51fa\uff1a[] \u89e3\u91ca\uff1a  a \u77e9\u9635\u4e2d\u67e5\u627e\uff0c\u8fd4\u56de []\u3002 <\/code><\/pre>\n
\u9898\u89e3<\/h2>\n
\u4f7f\u7528 HashMap \u7684\u7248\u672c\u3002 \u5c06\u6240\u6709\u7684\u5355\u8bcd\u7684 Prefix \u90fd\u52a0\u5165 HashMap \u4e2d\u3002HashMap \u7684 value \u7528\u6237\u5224\u65ad\u8fd9\u662f\u4e00\u4e2a prefix \u8fd8\u662f\u4e00\u4e2a word \u3002 \u5982\u679c\u662f prefix \u5c31\u662f false\uff0c\u5982\u679c\u662f word \u5c31\u662f true.<\/p>\n
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;     } }  <\/code><\/pre>\n<\/p><\/div>\n
 \u5927\u4f6c\u6709\u8a71\u8aaa<\/b> (0<\/span>)        <\/div>\n
 <\/div>\n<\/p><\/div>\n<\/p><\/div>\n
    \n
  • \n","protected":false},"excerpt":{"rendered":"
    Google \u9762\u8bd5\u9898\uff1a\u5355\u8bcd\u641c\u7d22 I…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[],"tags":[],"_links":{"self":[{"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/posts\/159874"}],"collection":[{"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/4563.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=159874"}],"version-history":[{"count":0,"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/posts\/159874\/revisions"}],"wp:attachment":[{"href":"http:\/\/4563.org\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=159874"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/4563.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=159874"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/4563.org\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=159874"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}