가사에 사용된 모든 단어들이 담긴 배열 words와 찾고자 하는 키워드가 담긴 배열 queries가 주어질 때, 각 키워드 별로 매치된 단어가 몇 개인지 순서대로 배열에 담아 반환하도록 solution 함수를 완성해 주세요.

가사 단어 제한사항

words의 길이(가사 단어의 개수)는 2 이상 100,000 이하입니다.
각 가사 단어의 길이는 1 이상 10,000 이하로 빈 문자열인 경우는 없습니다.
전체 가사 단어 길이의 합은 2 이상 1,000,000 이하입니다.
가사에 동일 단어가 여러 번 나올 경우 중복을 제거하고 words에는 하나로만 제공됩니다.
각 가사 단어는 오직 알파벳 소문자로만 구성되어 있으며, 특수문자나 숫자는 포함하지 않는 것으로 가정합니다.

검색 키워드 제한사항

queries의 길이(검색 키워드 개수)는 2 이상 100,000 이하입니다.
각 검색 키워드의 길이는 1 이상 10,000 이하로 빈 문자열인 경우는 없습니다.
전체 검색 키워드 길이의 합은 2 이상 1,000,000 이하입니다.
검색 키워드는 중복될 수도 있습니다.
각 검색 키워드는 오직 알파벳 소문자와 와일드카드 문자인 '?' 로만 구성되어 있으며, 특수문자나 숫자는 포함하지 않는 것으로 가정합니다.
검색 키워드는 와일드카드 문자인 '?'가 하나 이상 포함돼 있으며, '?'는 각 검색 키워드의 접두사 아니면 접미사 중 하나로만 주어집니다.
예를 들어 "??odo", "fro??", "?????"는 가능한 키워드입니다.
반면에 "frodo"('?'가 없음), "fr?do"('?'가 중간에 있음), "?ro??"('?'가 양쪽에 있음)는 불가능한 키워드입니다.

처음 생각한것

정규식 문제인가?라고 생각했다. 간단히 정규식화해서 문제를 풀면될줄알았는데 효율성에서 문제가 생긴다.
이를 통해서 효율성을 생각하면 아마 이분탐색이거나 다른 방법이 있을거라 생각했지만 상당히 시간이 걸려서 다른사람의 코드를 빌려봤다.
이분탐색도 가능하지만 트리방식으로 문제를 푸는것도 가능해서 트리방식으로 문제를 해결했다.

실패코드 (완전탐색)

import java.util.*;

class Solution {
    public int[] solution(String[] words, String[] queries) {
        int[] answer = new int[queries.length];
        for(int i=0;i<queries.length;i++){
            String pre = queries[i].substring(0,queries[i].indexOf("?"));
            String post =queries[i].substring(queries[i].lastIndexOf("?")+1);
            int first = queries[i].indexOf("?");
            int last = queries[i].lastIndexOf("?");
            int count = last - first + 1;
            int idx=0;
          
            for(int j=0;j<words.length;j++){
                if(queries[i].length()!=words[j].length()) continue;
                if(pre.equals(words[j].substring(0,first))&&post.equals(words[j].substring(last+1))){
                    idx++;
                }
            }
            answer[i] = idx;
        }
       
        return answer;
    }
}

성공코드 트리

import java.util.*;
class Solution {
    public int[] solution(String[] words, String[] queries) {
        Trie front = new Trie();
        Trie back = new Trie();

        for (String word : words) {
            front.insert(word);
            back.insert(reverse(word));
        }
        int[] answer = new int[queries.length];
        for(int i=0;i<queries.length;i++){
            if(queries[i].charAt(0)=='?'){
                answer[i]= back.find(reverse(queries[i]),0);               
            }else{
                answer[i]= front.find(queries[i],0);
            }
          
        }
        return answer;
    }
    class Trie{
        HashMap<Integer,Integer> map = new HashMap<>();
        Trie[] trie = new Trie[26];
        
        int find(String str,int i){
            if(str.charAt(i)=='?') 
                return map.getOrDefault(str.length(),0);
            
            int idx = str.charAt(i) - 'a';
            int num = (trie[idx] == null ? 0 : trie[idx].find(str, i + 1));
            return num;            
        }
        
        void insert(String str){
            Trie node = this;
            int length =str.length();
            map.put(length, map.getOrDefault(length,0)+1);
            for(char ch : str.toCharArray()){
                int a = ch - 'a';
                if(node.trie[a]==null){
                    node.trie[a] = new Trie();
                }
                node = node.trie[a];
                node.map.put(length,node.map.getOrDefault(length,0)+1);
            }
        }
    }
    String reverse(String str){
        return new StringBuilder(str).reverse().toString();
    }
}//트리

앞으로 문제를 풀때는 먼저 효율성을 생각해야겠다.