99클럽 코테 스터디 15일차 TIL < Prefix and Suffix Search >

오늘의 문제

 

 

	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:

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

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

 

학습 키워드

 

---

 

Trie 알고리즘

---

 

문제 풀이

1. 주어진 words의 pref, suff 를 확인해가며 답을 도출
     - 문제 의도 파악 부터 잘못 되어 알고리즘 선행학습 후 재풀이 필요

 

---

틀린 코드

 

class WordFilter {
    private String[] words; 
    public WordFilter(String[] words) {
        this.words = words;
    }
    
    public int f(String pref, String suff) {
       int resultNum = -1;
	    	for(int i=0; i<words.length; i++) {
	    		int prefNum = words[i].indexOf(pref);
	    		int suffNum = words[i].indexOf(suff);
	    		
	    		if(prefNum != -1 && prefNum < suffNum ) {
	    			resultNum = i;
	    		}
	    	}
	    	return resultNum;
    }
}

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

 

 
 
오늘의 회고

 

문제 의도 파악과 알고리즘 선행 학습 필요