https://leetcode.com/problems/prefix-and-suffix-search/description/
[문제]
Design a special dictionary that searches the words in it by a prefix and a suffix.
Implement the WordFilter class:
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.
주어진 접두사와 접미사를 기준으로 구성이 가능한 단어의 가장 큰 인덱스를 반환하면 되는 문제입니다.
완전 탐색으로서, 이중 for문을 통해 구성했습니다.
미리 가능한 경우의 수를 다 구해놓고.. f 함수에서 원하는 요소를 추출하도록 구성했습니다.
먼저 코틀린 코드입니다.
class WordFilter(words: Array<String>) {
// 해시 맵을 사용하여 (prefix, suffix) 조합과 그에 해당하는 가장 큰 인덱스를 저장합니다.
private val prefixSuffixMap: MutableMap<String, Int> = mutableMapOf()
init {
// 모든 단어에 대해 가능한 모든 접두사와 접미사의 조합을 생성합니다.
for (index in words.indices) {
val word = words[index]
for (prefixLength in 0..word.length) {
for (suffixLength in 0..word.length) {
val prefix = word.substring(0, prefixLength)
val suffix = word.substring(word.length - suffixLength, word.length)
// 조합 키 생성
val key = "$prefix-$suffix"
// 해당 조합에 대한 가장 큰 인덱스 저장
prefixSuffixMap[key] = index
}
}
}
}
// 특정 접두사와 접미사를 사용하여 가장 큰 인덱스를 찾는 함수
fun f(pref: String, suff: String): Int {
val key = "$pref-$suff"
return prefixSuffixMap.getOrDefault(key, -1)
}
}접두사와 접미사에 대한 조합 가능한 경우들을 계산하여 선택된 단어 인덱스를 Map에 축적합니다.
그리고 각 조합에 대해 가장 큰 인덱스를 출력하게 됩니다.
