[LeetCode] - 2185. Counting Words With a Given Prefix

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

--> https://leetcode.com/problems/counting-words-with-a-given-prefix/description/

 

문제 : 

You are given an array of strings words and a string pref. Return the number of strings in words that contain pref as a prefix.

A prefix of a string s is any leading contiguous substring of s.

---

Example 1 :

Input : words = ["pay","attention","practice","attend"], pref = "at"

Output : 2

Explanation : The 2 strings that contain "at" as a prefix are: "attention" and "attend".

 

Example 2 :

Input : words = ["leetcode","win","loops","success"], pref = "code"

Output : 0

Explanation : There are no strings that contain "code" as a prefix.

 

Constraints :

• 1 <= words.length <= 100
• 1 <= words[i].length, pref.length <= 100 words[i] and pref consist of lowercase English letters.

---

이 문제는 주어진 문자열 배열 words에서 특정 접두사 pref를 포함하는 문자열의 개수를 반환하는 문제입니다. 접두사는 문자열의 시작 부분에 나타나는 연속적인 부분 문자열을 의미합니다.

class Solution {
    public int prefixCount(String[] words, String pref) {
        int prefLen = pref.length();
        int count = 0;

        for (int i = 0; i < words.length; i++) {
            if (words[i].length() >= prefLen && words[i].substring(0, prefLen).equals(pref)) {
                count++;
            }   
        }

        return count;
    }
}

 

저는 처음에는 substring과  equals 메소드를 써서 풀었는데 사실 이보다 더 효과적인 방법이 존재했습니다. 

제가 잊고 있었던 indexOf 라는 메소드인데요, 바로 보여드리겠습니다 :

class Solution {
    public int prefixCount(String[] words, String pref) {
        int count=0;
        for(String s : words){
            if(s.indexOf(pref)==0){
                count++;
            }
        }
        return count;
    }
}

 

전보다 훨씬 더 나은 코드가 되었습니다. 간단히 설명을 하자면 : 

 

주어진 문자열 배열 words에서 특정 접두사 pref를 포함하는 문자열의 개수를 반환하는 문제를 해결합니다. indexOf 메서드를 사용하여 문자열이 접두사로 시작하는지 확인하는 방식입니다.

1. 변수 초기화 :
   • int count = 0; 문장을 사용하여 접두사 pref로 시작하는 문자열의 개수를 카운트할 변수를 초기화합니다.
2. 문자열 배열 순회 :
   • for (String s : words) { ... } 문장을 사용하여 문자열 배열 words를 순회합니다.
   • 각 문자열 s에 대해 if (s.indexOf(pref) == 0) { ... } 문장을 사용하여 문자열이 접두사 pref로 시작하는지 확인합니다.
   • indexOf 메서드는 문자열 s에서 pref가 처음 나타나는 인덱스를 반환합니다. s.indexOf(pref) == 0이면 문자열 s의 시작 부분에 pref가 있다는 의미입니다.
   • 문자열이 접두사 pref로 시작하면 count를 1 증가시킵니다.
3. 결과 반환 :
   • 최종적으로 count 값을 반환합니다.

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

---

개선 되기 전 후 코드 Runtime 결과