国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

212. Word SearchII

hoohack / 2910人閱讀

摘要:題目解答這題我原來是在的基礎(chǔ)上,用來做的,代碼如下做完之后,結(jié)果運(yùn)行是對的,但是了,所以肯定是有更好的辦法。代碼如下去重

題目:
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"].

解答:
這題我原來是在word search I的基礎(chǔ)上,用backtracking來做的,代碼如下:

public boolean exist(char[][] board, String word, int i, int j, int pos, boolean[][] visited) {
    if (pos == word.length()) return true;
    if (i < 0 || i > board.length - 1 || j < 0 || j > board[i].length - 1) return false;
    if (visited[i][j] || board[i][j] != word.charAt(pos)) return false;
    
    visited[i][j] = true;
    int[][] dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    for (int k = 0; k < dir.length; k++) {
        int x = i + dir[k][0], y = j + dir[k][1];
        if (exist(board, word, x, y, pos + 1, visited)) {
            return true;
        }
    }
    visited[i][j] = false;
    return false;
}

public boolean helper(char[][] board, String word) {
    boolean[][] visited = new boolean[board.length][board[0].length];
    for (int i = 0; i < board.length; i++) {
        for (int j = 0; j < board[i].length; j++) {
            if (exist(board, word, i, j, 0, visited)) {
                return true;
            }
        }
    }
    return false;
}

public List findWords(char[][] board, String[] words) {
    List result = new ArrayList();
    if (board == null || board.length == 0 || board[0].length == 0) return result;
 
    for (String word : words) {
        if (helper(board, word)) {
            if (!result.contains(word)) {
                result.add(word);
            }
        }
    }
    
    return result;
}

做完之后,結(jié)果運(yùn)行是對的,但是TLE了,所以肯定是有更好的辦法。在TLE的test case里,我看到是當(dāng)prefix相同時,如果用backtracking那么會不斷地掃同一個位置的prefix,非常的冗余,那么怎么把prefix提取出來只掃一次呢?一個很好的辦法就是反過來,用trie樹先把單詞存起來,然后掃board,掃board的時候用trie樹中的可能出現(xiàn)的單詞作為限制條件,那么當(dāng)掃到一個trie中結(jié)尾存在的單詞時,把它存進(jìn)result中去。代碼如下:

class TrieNode {
    TrieNode[] next = new TrieNode[26];
    String word;
}

public TrieNode buildTrie(String[] words) {
    TrieNode root = new TrieNode();
    for (String word : words) {
        TrieNode p = root;
        for (char c : word.toCharArray()) {
            int i = c - "a";
            if (p.next[i] == null) p.next[i] = new TrieNode();
            p = p.next[i];
        }
        p.word = word;
    }
    return root;
}

public void dfs(List result, char[][] board, TrieNode p, int i, int j) {
    char c = board[i][j];
    if (c == "#" || p.next[c - "a"] == null) return;
    p = p.next[c - "a"];
    
    if (p.word != null) {
        result.add(p.word);
        p.word = null; //去重
    }
    
    board[i][j] = "#";
    int[][] dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    for (int k = 0; k < dir.length; k++) {
        int x = i + dir[k][0], y = j + dir[k][1];
        if (x < 0 || x > board.length - 1 || y < 0 || y > board[i].length - 1) continue;
        dfs(result, board, p, x, y);
    }
    board[i][j] = c;
}

public List findWords(char[][] board, String[] words) {
    List result = new ArrayList();
    if (board == null || board.length == 0 || board[0].length == 0) return result;
    
    TrieNode root = buildTrie(words);
    for (int i = 0; i < board.length; i++) {
        for (int j = 0; j < board[i].length; j++) {
            dfs(result, board, root, i, j);
        }
    }
    return result;
}

文章版權(quán)歸作者所有,未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址:http://specialneedsforspecialkids.com/yun/64976.html

相關(guān)文章

  • [LeetCode] 212. Word Search II

    Problem 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 ...

    Flands 評論0 收藏0
  • Vim session

    摘要:練級攻略的縱向編輯模式第一步修改將數(shù)列中第二段所有數(shù)字修改為將游標(biāo)定位第一個行的進(jìn)入縱向編輯模式移動游標(biāo)到最后一行,可視塊覆蓋所要修改的列進(jìn)入修改模式輸入數(shù)字第二步前添加在所有行之前添加將游標(biāo)定位到第一行第一列進(jìn)入縱向編輯模式 vimtutor showImg(https://segmentfault.com/img/bV4OLS?w=600&h=400); intro vim hi...

    nanfeiyan 評論0 收藏0
  • Bind進(jìn)階

    摘要:子域授權(quán)比如我的一臺服務(wù)器負(fù)責(zé)的權(quán)威域名解析,它再授權(quán)服務(wù)器對的子域名進(jìn)行解析,這就叫做子域授權(quán)。之后,通過自己的會話密鑰將要發(fā)送的明文進(jìn)行加密,發(fā)送給,通過事先得到的會話密鑰對發(fā)送過來的密文進(jìn)行解密從而得到明文。 還是出于項(xiàng)目的需要,把Bind比較高級的功能做一個梳理,這其中包含:DNS遞歸迭代查詢、DNS子域授權(quán)、DNS轉(zhuǎn)發(fā)、DNS主從區(qū)域傳輸、DNS數(shù)據(jù)加密,每一個內(nèi)容不僅記錄了...

    doodlewind 評論0 收藏0

發(fā)表評論

0條評論

閱讀需要支付1元查看
<