꿀잠

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;  
        }  
    }  
}