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

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

#### Hard

***

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`.

 

**Example 1:**

<pre><code><strong>Input
</strong>["WordFilter", "f"]
[[["apple"]], ["a", "e"]]
<strong>Output
</strong>[null, 0]
<strong>Explanation
</strong>WordFilter wordFilter = new WordFilter(["apple"]);
wordFilter.f("a", "e"); // return 0, because the word at index 0 has prefix = "a" and suffix = "e".
</code></pre>

&#x20;

**Constraints:**

* `1 <= words.length <= 104`
* `1 <= words[i].length <= 7`
* `1 <= pref.length, suff.length <= 7`
* `words[i]`, `pref` and `suff` consist of lowercase English letters only.
* At most `104` calls will be made to the function `f`.

### 문제 요약

주어진 문자열 배열에서 인수로 전달할 접두사와 접미사로 이루어진 문자열의 인덱스를 반환하는데 중복될 경우, 더 큰 인덱스 값을 반환하면 되는 문제입니다.

***

## 풀이 코드

```java
class WordFilter {

    private final String[] words;

    public WordFilter(String[] words) {
        this.words = words;
    }
    
    public int f(String pref, String suff) {
        int idx = -1;
        for (int i = words.length - 1; i > -1; i--) {
            String word = words[i];
            if (word.charAt(0) != pref.charAt(0)) continue;
            if (word.startsWith(pref) && word.endsWith(suff)) {
                idx = i;
                break;
            }
        }
        return idx;
    }
}

/**
 * Your WordFilter object will be instantiated and called as such:
 * WordFilter obj = new WordFilter(words);
 * int param_1 = obj.f(pref,suff);
 */
```

* Time: 1363 ms
* Space: 57.7 MB

제한 사항이 문자열 배열의 크기가 최대 10만개까지여서 시간 초과로 계속 실패했다. 중복될 경우 더 큰 인덱스 값을 반환하면 되니까 일단 문자열 배열을 뒤에서부터 순회하도록 했다.

그래도 시간 초과가 떠서 문자열의 첫번째 문자와 접두사의 첫번째 문자가 다르면 비교할 의미가 없기 때문에 바로 `continue` 시켜주는 조건문을 작성하니까 정말 턱걸이로 통과했다.

해당 문제는 Trie 알고리즘을 활용하거나 `HashMap` 에 문자열에 대한 모든 접두사와 접미사 조합을 `key` 로 추가하는 방법도 있다.

두 방법에 대해선 스스로 더 공부한 후에 공유하도록 하겠다.

***

## 돌아보기

이중 반복문을 너무 배제시켰던 것 같다. 시간 복잡도를 생각하면서 풀어봐야겠다.

### 다음에는

* 이중 `for` 문과 친해지기
* 시간 복잡도도 생각하기
* 자료구조 좀 활용하기

***

\#99클럽 #코딩테스트준비 #개발자취업 #항해99 #TIL


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://devlee.gitbook.io/docs/study/99/99-15-til-leetcode-prefix-and-suffix-search.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.