8월 5일 99클럽 항해 15일

99클럽 항해 15일차

 

오늘의 문제는  Prefix and Suffix Search이다.

 

• WordFilter(string[] words) Initializes the object with the words in the dictionary.

• f(string pref, string suff) Returns the index of the word in the dictionary, which has the prefix pref and the suffix suff. If there is more than one valid index, return the largest of them. If there is no such word in the dictionary, return -1.

문제에서 주어진 두 값을 비교하여 값이 있으면 해당 값이 몇개가 있는지 수를 체크하는 문제가 되겠다.

WordFilter 생성자는 사전안의 단어 객체를 초기화하고, f 메서드는 pref(접두사), suff(접미사)를 가진 사전 내부의 단어중 제일 큰 인덱스를 출력한다.

   

prefix + "#" + suffix 형식의 문자열을 키로 하고, 해당 조합과 일치하는 단어의 인덱스를 값으로 맵을 저장한다.

 

단어의 특정 부분을 문자열로 만들고 단어의 특정 부분부터 문자열을 생성하여 접두사와 접미사를 생성하고,

조합된 단어와 해당 조합에 대한 현재 단어의 인덱스를 저장한다.

같은 조합이 이미 해시맵에 존재한다면 인덱스를 덮어 씌워 더 큰 값 해시맵의 값으로 가지게 된다.

 

키가 해시맵에 존재하면, 해당 값을 반환하고 없다면 -1을 반환한다.

 

 

import java.util.*;

class WordFilter {

    private Map<String, Integer> map;

    public WordFilter(String[] words) {
        map = new HashMap<>();
        
        // 모든 단어에 대해 가능한 모든 접두사와 접미사 조합을 저장
        for (int i = 0; i < words.length; i++) {
            String word = words[i];
            int len = word.length();

            // 모든 접두사와 접미사 조합을 생성하고 저장
            for (int j = 0; j <= len; j++) {
                String prefix = word.substring(0, j);
                for (int k = 0; k <= len; k++) {
                    String suffix = word.substring(len - k);
                    map.put(prefix + "#" + suffix, i);
                }
            }
        }
    }

    public int f(String prefix, String suffix) {
        String key = prefix + "#" + suffix;
        return map.getOrDefault(key, -1);
    }
}