[Leetcode] 오늘의 문제 - 2416. Sum of Prefix Scores of Strings

문제

2416. Sum of Prefix Scores of Strings

 

You are given an array words of size n consisting of non-empty strings.
We define the score of a string word as the number of strings words[i] such that word is a prefix of words[i].
For example, if words = ["a", "ab", "abc", "cab"], then the score of "ab" is 2, since "ab" is a prefix of both "ab" and "abc".

Return an array answer of size n where answer[i] is the sum of scores of every non-empty prefix of words[i].

Note that a string is considered as a prefix of itself.

 

키워드

Array
String
Trie
Counting

 

 

내 첫번째 접근

• 이중 for문으로 prefix를 주어진 문자열 배열과 비교해서 카운트하는 로직을 생각했다.
• 결과 : Time Limit Exceeded

class Solution {
    public int prefixScore(String[] words, String str) {
        int count = 0;

        for (int i = 1; i <= str.length(); i++) {
            String prefix = str.substring(0, i);

            for (int j = 0; j < words.length; j++) {
                if (words[j].startsWith(prefix)) {
                    count++;
                }
            }
        }
        return count;
    }

    public int[] sumPrefixScores(String[] words) {
        int len = words.length;
        int[] result = new int[len];

        for (int i = 0; i < len; i++) {
            result[i] = prefixScore(words, words[i]);
        }
        
        return result;
    }
}

 

 

다른 접근 풀이

• 시간 복잡도를 줄이기 위해 Trie를 사용해보자.