꿀잠

https://leetcode.com/problems/replace-words/description/

주어진 사전의 단어를 이용하여 주어진 문장 내의 문자열을 사전 속 단어로 변경하는 문제이다.
Trie 자료구조를 이용할 수 있다. 주어진 사전의 단어들을 저장한 이후, 문장 내에서 해당 단어를 prefix로 갖고 있는 단어들을 교환해준다. 단어를 검사하며 길이를 확인하고 substring 하여 문자열을 대체해주었다.

import java.util.*;  
  
public class Solution {  
    public String replaceWords(List<String> dictionary, String sentence) {  
        Trie root = new Trie();  
  
        for(String word: dictionary){  
            Trie head = root;  
            for(int i = 0; i < word.length(); i++){  
                char c = word.charAt(i);  
                if(head.next[c - 'a'] == null){  
                    head.next[c - 'a'] = new Trie();  
                }  
                head = head.next[c - 'a'];  
  
                if(i == word.length() - 1){  
                    head.isLast = true;  
                }  
            }  
        }  
  
        String[] sentenceArr = sentence.split(" ");  
        for(int i = 0; i < sentenceArr.length; i++){  
            String word = sentenceArr[i];  
            Trie head = root;  
            int length = 0;  
            for(int j = 0; j < word.length(); j++){  
                char c = word.charAt(j);  
                if(head.next[c - 'a'] == null) break;  
                head = head.next[c - 'a'];  
                length++;  
                if(head.isLast){  
                    sentenceArr[i] = word.substring(0, length);  
                    break;  
                }  
            }  
        }  
  
        StringBuilder sb = new StringBuilder();  
        for(String word: sentenceArr){  
            sb.append(word);  
            sb.append(" ");  
        }  
        return sb.toString().trim();  
    }  
  
    private static class Trie{  
        Trie[] next;  
        boolean isLast;  
  
        Trie(){  
            next = new Trie[26];  
            isLast = false;  
        }  
    }  
}

주어진 문자열 배열의 최대 길이의 동일 prefix 를 찾는 문제이다.
로드맵상 Trie 문제로 열심히 풀었으나... 사실 단순히 String 클래스의 startsWith 메서드를 쓰는게 더 편하다는 사실을 후에 알았다.

그럼에도 일단 문제를 통과했으니 해결한 코드를 소개한다.
Trie 구조에 repeat이란 int 값을 추가해주었다. 저장되는 문자들의 동일한 문자가 반복 저장되는 부분을 추가해준 것이다. 따라서 repeat 값을 보면 해당 문자까지 동일한 prefix를 갖는 문자열의 개수를 알 수 있다. 아래는 완성코드이다.

public class Solution {  
    public String longestCommonPrefix(String[] strs) {  
        Trie root = new Trie();  
        for(String str: strs){  
            Trie head = root;  
            char[] c = str.toCharArray();  
            for(int i = 0; i < c.length; i++){  
                int check = c[i] - 'a';  
                if(head.next[check] == null){  
                    head.next[check] = new Trie();  
                }else{  
                    head.next[check].repeat++;  
                }  
                head = head.next[check];  
            }  
        }  
  
        StringBuilder sb = new StringBuilder();  
        Trie head = root;  
        while(head != null){  
            Trie[] next = head.next;  
            boolean isExist = false;  
            for(int i = 0; i < next.length; i++){  
                if(next[i] != null && next[i].repeat == strs.length){  
                    isExist = true;  
                    sb.append(Character.toString(i + 'a'));  
                    head = next[i];  
                    break;  
                }  
            }  
  
            if(!isExist) break;  
        }  
  
        return sb.toString();  
    }  
  
    private static class Trie{  
        Trie[] next;  
        int repeat;  
  
        Trie(){  
            next = new Trie[26];  
            repeat = 1;  
        }  
    }  
}

https://leetcode.com/problems/word-search-ii/description/

보드의 문자열을 순회하며 단어를 만들 수 있는지 확인하는 문제이다.
보드의 문자를 순차적으로 연결하는 문제이기에 초기에 백트래킹을 이용하여 해결하려고 시도했다.

하지만 찾아야 하는 단어가 배열로 많이 주어지고,같은 prefix를 갖는 단어들이 주어지는 테스트 케이스가 존재하여 시간 초과가 되었다. 이를 해결하기 위해 Trie 자료구조를 이용했다. 아래는 완성한 통과 코드이다.

import java.util.*;  
  
public class Solution {  
  
    Set<String> answerSet;  
    char[][] board;  
    boolean[][] visited;  
    int[] dr = {-1, 0, 1, 0};  
    int[] dc = {0, -1, 0, 1};  
    int m;  
    int n;  
  
    public List<String> findWords(char[][] board, String[] words) {  
        this.board = board;  
        this.m = board.length;  
        this.n = board[0].length;  
        this.visited = new boolean[m][n];  
        TrieNode root = new TrieNode();  
        answerSet = new HashSet<>();  
  
        for(String word: words){  
            TrieNode head = root;  
            for(int i = 0; i < word.length(); i++){  
                char c = word.charAt(i);  
                int check = c - 'a';  
                if(head.next[check] == null){  
                    head.next[check] = new TrieNode();  
                }  
                TrieNode next = head.next[check];  
  
                head = next;  
                if(i == word.length() - 1){  
                    head.isLast = true;  
                }  
            }  
        }  
  
        StringBuilder sb = new StringBuilder();  
        for(int i = 0; i < m; i++){  
            for(int j = 0; j < n; j++){  
                visited[i][j] = true;  
                sb.append(board[i][j]);  
                findWord(root, i, j, sb);  
                visited[i][j] = false;  
                sb.setLength(sb.length() - 1);  
            }  
        }  
  
        return new ArrayList<>(answerSet);  
    }  
  
    private void findWord(TrieNode head, int r, int c, StringBuilder sb){  
        char ch = board[r][c];  
        int check = ch - 'a';  
        if(head.next[check] == null){  
            return;  
        }  
  
        head = head.next[check];  
  
        if(head.isLast){  
            answerSet.add(sb.toString());  
        }  
  
        for(int k = 0; k < dr.length; k++){  
            int nextRow = r + dr[k];  
            int nextCol = c + dc[k];  
            if(nextRow >= 0 && nextRow < m  
                    && nextCol >= 0 && nextCol < n  
                    && !visited[nextRow][nextCol]){  
                visited[nextRow][nextCol] = true;  
                sb.append(board[nextRow][nextCol]);  
                findWord(head, nextRow, nextCol, sb);  
                visited[nextRow][nextCol] = false;  
                sb.deleteCharAt(sb.length() - 1);  
            }  
        }  
    }  
  
    private static class TrieNode{  
        TrieNode[] next;  
        boolean isLast;  
  
        TrieNode(){  
            next = new TrieNode[26];  
            isLast = false;  
        }  
    }  
  
}

중복되는 정답을 정리하기 위해 Set을 이용해주었다. 해결한 이후 보다 빠른 통과 코드를 확인해보았다. 다른 점은 TrieNode에 isLast 대신 String word를 넣어주는 방법이었다. word를 저장시 isLast 지점에서 word 자체를 저장하는 방식이었다.

    private static class TrieNode{  
        TrieNode[] next;  
        String word;  
  
        TrieNode(){  
            next = new TrieNode[26];   
        }  
    }  
}

해당 클래스에 word를 넣어주면 백트래킹 탐색시 문자열 검색이 쉬워지는 장점이 있다. 또한 Set을 이용할 필요 없이 word를 지워주는 방식으로 중복을 제거할 수 있었다. Trie 구조가 익숙하지 않았었기에 새로운 사용 방식을 배울 수 있었다.

https://leetcode.com/problems/implement-trie-prefix-tree/description/

문자열을 저장하고 검색하는 Trie 클래스를 만드는 문제이다. 단순하게 List 클래스를 이용하여 해결해 주었다. insert 와 search의 경우 ArrayList 클래스의 기본 메서드를 이용해 주었으며
검색 시에는 리스트를 순회하며 substring 하여 prefix와 substring 한 결과를 비교해주었다.

public class Trie {  
  
    List<String> list;  
  
    public Trie() {  
        list = new ArrayList<>();  
    }  
  
    public void insert(String word) {  
        list.add(word);  
    }  
  
    public boolean search(String word) {  
        return list.contains(word);  
    }  
  
    public boolean startsWith(String prefix) {  
        for(int i = 0; i < list.size(); i++){  
            String str = list.get(i);  
            if(str.length() >= prefix.length()  
                    && str.substring(0, prefix.length()).equals(prefix)) return true;  
        }  
  
        return false;  
    }  
}  
  
/**  
 * Your Trie object will be instantiated and called as such: 
   * Trie obj = new Trie(); 
     * obj.insert(word); 
       * boolean param_2 = obj.search(word); 
         * boolean param_3 = obj.startsWith(prefix); 
           */