99클럽 코테 스터디 15일차 TIL + 오늘의 학습 키워드

☑️ 문제: 

https://leetcode.com/problems/prefix-and-suffix-search/submissions/1345477997/

 

시도해보았지만, 시간 초과가 나면서 통과되지 않더라.

☑️ Fail: 시간초과 나는 코드 

String.startWith, endWith을 사용하면 시간 초과가 발생한다. (6/17 통과)

class WordFilter {
    private String[] words;

    public WordFilter(String[] words) {
        this.words = words;
    }
    
    public int f(String pref, String suff) {
        int index = -1; 
        for(int i = 0; i < this.words.length; i++){
            if(words[i].startsWith(pref) && words[i].endsWith(suff)){
                index = Math.max(index, i);
            }
        }
        return index;
    }
}

 

시간 초과(13/17 통과)

class WordFilter {
    private String[] words;

    public WordFilter(String[] words) {
        // Initializes the object 
        this.words = words;
    }
    
    public int f(String pref, String suff) {
        // pref, suff를 만족하는 words[i] 중 largest index return (없으면 -1)
        int index = -1; 
        int pLen = pref.length();
        int sLen = suff.length();
        String str1 = pref + suff;
        for(int i = words.length - 1; i >= 0; i--) {
            int wLen = words[i].length();
            if (wLen < Math.max(pLen, sLen)) {
                continue;
            }

            if (str1.equals(words[i].substring(0, pLen) + words[i].substring(wLen - sLen, wLen))) {
                index = i;
                break;
            }
        }
        return index;
    }
}

 

☑️ 다른 사람 풀이 참고

https://github.com/Alex-XJK/Code-Journey/blob/main/Leetcode-745.%20Prefix%20and%20Suffix%20Search@Java.java

위 코드를 참고해서 풀었더니 통과되었다.