99클럽 코테 스터디 15일차 TIL - [LeetCode] Prefix and Suffix Search (Java)

📌 오늘의 학습 키워드

[LeetCode] Prefix and Suffix Search (Java)
https://leetcode.com/problems/prefix-and-suffix-search/

📌 공부한 내용 본인의 언어로 정리하기

문제 탐색하기

입력 : 단어 배열 String[] words
출력 : 특정 접두사와 접미사를 가진 단어의 인덱스를 찾아 반환, 없으면 -1을 반환

가능한 시간복잡도

O(n)

알고리즘 선택

완전 탐색

📌 코드 설계하기

1. HashMap을 사용하여 각 단어의 접두사와 접미사의 조합과 그에 해당하는 인덱스를 저장한다.
2. 생성자 WordFilter(String[] words)에서 입력으로 주어진 단어 배열 words의 각 단어에 대해 반복한다.
3. 각 단어에 대해 가능한 모든 접두사와 접미사를 생성한다.
4. 접두사와 접미사를 "prefix#suffix" 형식의 키로 해서 맵에 저장한다. 최신(가장 높은) 인덱스가 저장되도록 한다.
5. 메소드 f(String prefix, String suffix)에서 주어진 접두사와 접미사를 #로 연결해 키를 생성한다.
6. 이 키가 맵에 있는지 확인하고, 있으면 저장된 인덱스를 반환하며, 없으면 -1을 반환한다.

📌 오늘의 회고

어떤 문제가 있었고, 나는 어떤 시도를 했는지

어떻게 해결했는지

무엇을 새롭게 알았는지

내일 학습할 것은 무엇인지

구현

📌 정답 코드

import java.util.*;

class WordFilter {
    private Map<String, Integer> map;

    public WordFilter(String[] words) {
        map = new HashMap<>();
        for (int index = 0; index < words.length; index++) {
            String word = words[index];
            int length = word.length();
            for (int prefixLength = 0; prefixLength <= length; prefixLength++) {
                String prefix = word.substring(0, prefixLength);
                for (int suffixLength = 0; suffixLength <= length; suffixLength++) {
                    String suffix = word.substring(suffixLength);
                    map.put(prefix + "#" + suffix, index);
                }
            }
        }
    }
    
    public int f(String prefix, String suffix) {
        String key = prefix + "#" + suffix;
        return map.getOrDefault(key, -1);
    }
}

public class Main {
    public static void main(String[] args) {
        // Initialize the WordFilter with a list of words
        String[] words = {"apple"};
        WordFilter wf = new WordFilter(words);
        
        // Call the f method and print the result
        System.out.println(wf.f("a", "e")); // Expected output: 0
        System.out.println(wf.f("b", ""));  // Expected output: -1
    }
}