[Leetcode Top Interview 150] 212. Word Search II

난이도 : hard

문제링크

• 2차원 문자 배열 board와 문자열 배열 words가 주어짐
• board에 존재하는 모든 word를 리턴하라 
  • word는 words에 해당하는 문자열을 가리킴
  • board에 인접한 문자들을 가지고 word를 만들 수 있음

 

1. 접근법

• 모든 좌표를 시작점으로 word가 될 수 있는지 확인한다
• 인접한 문자들로 구성된 문자열이 word라면 결과에 추가한다

 

3. 구현 코드

int r, c, wordIdx;
char ch1;
int[] dy, dx;
Set<String> answer;
public List<String> findWords(char[][] board, String[] words) {
    r = board.length;
    c = board[0].length;
    dy = new int[] {1, 0, -1, 0};
    dx = new int[] {0, 1, 0, -1};
    answer = new HashSet<>();

    for (String word : words) {
        if (word.length() > r*c) {
            continue;
        }
        wordIdx = 0;
        ch1 = word.charAt(wordIdx);

        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                if (board[i][j] == ch1) {
                    boolean[][] visited = new boolean[r][c];
                    dfs(i, j, board, wordIdx, word, visited);
                }
            }
        }
    }

    return answer.stream().collect(Collectors.toList());
}

private boolean dfs(int y, int x, char[][] board, int idx, String word, boolean[][] visited) {
    if (!validate(y, x, board, idx, word, visited)) {
        return false;
    }

    if (idx == word.length()-1) {
        answer.add(word);
        return true;
    }

    visited[y][x] = true;

    for (int k = 0; k < 4; k++) {
        int ny = y + dy[k];
        int nx = x + dx[k];
        int ni = idx + 1;

        if (dfs(ny, nx, board, ni, word, visited)) {
            return true;
        }
    }

    visited[y][x] = false;

    return false;
}

private boolean validate(int y, int x, char[][] board, int idx, String word, boolean[][] visited) {
    if (y < 0 || y > r-1 || x < 0 || x > c-1) {
        return false;
    }

    if (visited[y][x]) {
        return false;
    }

    if (board[y][x] != word.charAt(idx)) {
        return false;
    }

    return true;
}

• 방문한 점을 백트래킹하여 dfs 탐색한다
• 시간초과로 실패

 

6. 회고

• 모르겠어서 강의를 들었다

class TrieNode {
    Map<Character, TrieNode> map;
    boolean isWord;

    TrieNode() {
        this.map = new HashMap<>();
        this.isWord = false;
    }
}
TrieNode trie;
List<String> res;
int m, n;
char[][] board;
boolean[][] visited;
public List<String> solutionFindWords(char[][] board, String[] words) {
    trie = new TrieNode();
    res = new ArrayList<>();
    this.board = board;
    m = board.length;
    n = board[0].length;
    for (String word : words) {
        insertAWord(word);
    }

    for (int r = 0; r < m; r++) {
        for (int c = 0; c < n; c++) {
            char curC = board[r][c];
            visited = new boolean[m][n];
            dfs(r, c, new StringBuilder(), trie);
        }
    }

    return res;
}

private void insertAWord(String word) {
    char[] cArr = word.toCharArray();
    TrieNode curNode = trie;
    for (char curC : cArr) {
        if (!curNode.map.containsKey(curC)) {
            curNode.map.put(curC, new TrieNode());
        }
        curNode = curNode.map.get(curC);
    }
    curNode.isWord = true;
}

private void dfs(int r, int c, StringBuilder sb, TrieNode curTrie) {
    if (r < 0 || r == m || c < 0 || c == n) return;
    if (visited[r][c]) return;
    char curC = board[r][c];
    if (!curTrie.map.containsKey(curC)) return;
    sb.append(curC);
    curTrie = curTrie.map.get(curC);
    visited[r][c] = true;

    if (curTrie.isWord) {
        res.add(sb.toString());
        curTrie.isWord = false;
    }

    dfs(r, c+1, sb, curTrie);
    dfs(r, c-1, sb, curTrie);
    dfs(r+1, c, sb, curTrie);
    dfs(r-1, c, sb, curTrie);

    sb.setLength(sb.length()-1);
    visited[r][c] = false;
}

(출처 : Eric Programming)

• trie 자료구조를 사용하여 word를 보관한다
• dfs 탐색으로 trie에 word가 있는지 확인한다
  • word가 있다면, 해당 word를 answer에 저장하고 isWord를 false로 업데이트한다
    • 이미 체크된 단어이므로 다른 점에서 다시 단어체크하지 않도록 하기 위함
  • 다음 호출에서 이전 호출이 영향을 받지 않도록 하기 위해 백트래킹을 적용한다
    • visited는 탐색한 곳을 다시 원래대로 복구해주어야 다음 시작점에서 탐색할 때 새걸로 사용할 수 있다.
    • stringbuilder도 조건을 만족한다면 trie를 계속해서 깊게 파지만, 현재 깊이에서 모든 방향으로 탐색해서 체크할 수 있는 것들을 다 확인했다면 다음 호출이 영향을 받지 않도록 추가했던 길이를 원래대로 돌려둔다.