[LeetCode] - 2255. Count Prefixes of a Given String

LeetCode는 프로그래밍 문제를 풀며 코딩 실력을 향상할 수 있는 온라인 플랫폼입니다. 다양한 알고리즘 및 데이터 구조 문제를 제공하며, 면접 대비에 유용합니다. 해당 문제는, LeetCode Problems에서 볼 수 있는 난이도 '쉬움 (Easy)' 단계인 "Count Prefixes of a Given String" 문제입니다.

--> https://leetcode.com/problems/count-prefixes-of-a-given-string/description/

 

문제 : 

You are given a string array words and a string s, where words[i] and s comprise only of lowercase English letters.

Return the number of strings in words that are a prefix of s.

A prefix of a string is a substring that occurs at the beginning of the string. A substring is a contiguous sequence of characters within a string.

---

Example 1 :

Input : words = ["a","b","c","ab","bc","abc"], s = "abc"

Output : 3

Explanation : The strings in words which are a prefix of s = "abc" are: "a", "ab", and "abc".

Thus the number of strings in words which are a prefix of s is 3.

 

Example 2 :

Input : words = ["a","a"], s = "aa"

Output : 2

Explanation : Both of the strings are a prefix of s.

Note that the same string can occur multiple times in words, and it should be counted each time.

 

Constraints :

• 1 <= words.length <= 1000
• 1 <= words[i].length, s.length <= 10
• words[i] and s consist of lowercase English letters only.

---

이 문제는 주어진 문자열 배열 words와 문자열 s에서 words의 문자열 중 s의 접두사(prefix)인 문자열의 개수를 반환하는 문제입니다. 접두사는 문자열의 시작 부분에 나타나는 연속적인 부분 문자열을 의미합니다.

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

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

 

이 문제도 String 에 탑재되어있는 메소드를 잘 알고 계신 분이라면, 또, 자바로 코딩을 하시는 분이라면 바로 오 쉬운데 ? 하고 풀 수 있었던 문제입니다. 너무 반칙 아닌가 싶기도 합니다. 

그래도 설명을 드리겠습니다 : 

 

이 코드는 주어진 문자열 배열 words에서 특정 문자열 s의 접두사(prefix)인 문자열의 개수를 카운트하여 반환하는 문제를 해결합니다. 각 문자열을 순회하면서 s의 접두사인지 확인하는 방식입니다.

주요 단계 설명

1. 변수 초기화 :
   • int count = 0; 문장을 사용하여 접두사로 확인된 문자열의 개수를 카운트할 변수를 초기화합니다.
2. 문자열 배열 순회 :
   • for (int i = 0; i < words.length; i++) { ... } 문장을 사용하여 문자열 배열 words를 순회합니다.
   • 각 문자열 words[i]에 대해 if (s.startsWith(words[i])) { ... } 문장을 사용하여 문자열 words[i]가 문자열 s의 접두사인지 확인합니다.
   • 문자열이 접두사로 확인되면 count를 1 증가시킵니다.
3. 결과 반환 :
   • 최종적으로 count 값을 반환합니다.

• 시간 복잡도 : O(n * m)
  • 여기서 n은 배열 words의 길이이고, m은 문자열 s의 길이입니다.
  • 문자열 배열 words를 한 번 순회하면서 각 문자열의 접두사를 확인하기 때문에 시간 복잡도는 O(n * m)입니다.
  • startsWith 메서드는 최악의 경우 접두사 words[i]의 길이만큼 문자를 비교하므로 각 호출에 대해 O(m) 시간이 걸립니다.
• 공간 복잡도 : O(1)
  • 추가적인 배열이나 리스트를 사용하지 않고, 상수 공간만 사용하므로 공간 복잡도는 O(1)입니다.

---

코드 Runtime 결과