Jan 9, 2025

2185. Counting Words With a Given Prefix

내 코드

문자열.

0ms, 13.14MB

class Solution {
public:
    int prefixCount(vector<string>& words, string pref) {
        int answer{};
        for(string& word : words) {
            if(word.length() < pref.length()) continue;
            bool chk{};
            for(int i{}; i< pref.length();++i) {
                if(word[i] != pref[i]) {
                    chk = true; break;
                }
            }
            if(!chk) ++answer;
        }
        return answer;
    }
};

Solution

Approach 1: Brute Force

0ms, 13.14MB
Complexity
- Let $n$ be the length of the input array words and $m$ be the length of the prefix string pref.
- Time Complexity: $O(n \cdot m)$
- Space Complexity: $O(1)$

class Solution {
public:
    int prefixCount(vector<string>& words, string pref) {
        int count = 0;
        for (string& word : words) {
            count += hasPrefix(word, pref);
        }
        return count;
    }

private:
    // Returns 1 if str has pref as prefix, 0 otherwise
    int hasPrefix(string& str, string& pref) {
        int itr;
        // Compare characters until we reach the end of either string
        for (itr = 0; itr < str.length() && itr < pref.length(); itr++) {
            if (str[itr] != pref[itr]) {
                return 0;  // Mismatch found
            }
        }

        // Check if we've matched the entire prefix
        if (itr != pref.length()) {
            return 0;  // str is shorter than pref
        }
        return 1;
    }
};

GPT (o3-mini-high)

이 코드는 주어진 문자열 벡터(words)에서 특정 접두사(pref)로 시작하는 단어의 개수를 세는 기능을 수행합니다. 코드를 단계별로 설명하면 다음과 같습니다.

1. `prefixCount` 함수

int prefixCount(vector<string>& words, string pref) {
    int count = 0;
    for (string& word : words) {
        count += hasPrefix(word, pref);
    }
    return count;
}

입력 인자:
- words: 문자열들이 담긴 벡터.
- pref: 접두사로 확인할 문자열.
동작:
- count 변수를 0으로 초기화합니다.
- words 벡터에 포함된 각 문자열 word에 대해 hasPrefix 함수를 호출합니다.
- hasPrefix 함수는 해당 문자열이 pref로 시작하면 1, 그렇지 않으면 0을 반환합니다.
- 반환된 값들을 count에 누적하여 접두사와 일치하는 단어의 개수를 셉니다.
- 마지막에 count를 반환합니다.

2. `hasPrefix` 함수

int hasPrefix(string& str, string& pref) {
    int itr;
    // 두 문자열의 각 문자를 비교 (두 문자열 중 짧은 길이만큼 반복)
    for (itr = 0; itr < str.length() && itr < pref.length(); itr++) {
        if (str[itr] != pref[itr]) {
            return 0;  // 불일치하는 문자가 발견되면 접두사가 아님
        }
    }

    // 반복문이 끝난 후, pref의 모든 문자가 비교되었는지 확인
    if (itr != pref.length()) {
        return 0;  // str이 pref보다 짧아서 모든 문자를 비교할 수 없으므로 접두사가 아님
    }
    return 1;  // 모든 문자가 일치하면 접두사임
}

입력 인자:
- str: 검사할 문자열.
- pref: 접두사로 확인할 문자열.
동작:
- 변수 itr를 사용하여 두 문자열의 각 문자를 인덱스 0부터 비교합니다.
- 반복문 조건: itr < str.length() && itr < pref.length()
  → 두 문자열 중 짧은 길이만큼 반복하여 비교합니다.
- 문자 비교:
  - 만약 str[itr]와 pref[itr]가 다르면, 바로 0을 반환합니다. (즉, str이 pref로 시작하지 않음을 의미)
- 반복 후 확인:
  - 반복문이 종료된 후 itr 값이 pref.length()와 같지 않으면, str의 길이가 pref보다 짧았음을 의미하므로 0을 반환합니다.
- 모든 조건을 만족한 경우:
  - 위의 모든 비교가 통과되면 str은 pref를 접두사로 가지므로 1을 반환합니다.

전체 동작 요약

prefixCount 함수는 주어진 words 벡터의 각 문자열에 대해 hasPrefix 함수를 호출합니다.
hasPrefix 함수는 해당 문자열이 pref로 시작하는지 문자 단위로 확인합니다.
접두사가 일치하면 1, 그렇지 않으면 0을 반환하고, 이를 모두 합산하여 최종적으로 접두사와 일치하는 문자열의 총 개수를 반환합니다.

이 코드의 핵심은 문자열의 접두사 여부를 직접 비교하여 판별하는 간단하면서도 효율적인 방법을 사용한다는 점입니다.

Approach 2: Built-In Methods

0ms, 13.06MB
Complexity
- Let $n$ be the length of the input array words and $m$ be the length of the prefix string pref.
- Time Complexity: $O(n \cdot m)$
- Space Complexity: $O(1)$

class Solution {
public:
    int prefixCount(vector<string>& words, string pref) {
        int count = 0;
        for (string& word : words) {
            if (word.find(pref) == 0) {
                count++;  // Found a string with pref as prefix
            }
        }
        return count;
    }
};

C++

std::string::find (or std::string::rfind)
: Finds the position of the first or last occurrence of a substring and is commonly used to check if it occurs at the start.
std::string::substr(size_t pos, size_t len)
: Extracts a substring starting at a position, which can be used to compare the prefix manually.
std::mismatch (from <algorithm>)
: Compares elements of two ranges (e.g., a prefix and the beginning of a string) and determines if they match.

GPT (o3-mini-high)

이 코드는 주어진 문자열 벡터(words) 내에서 특정 접두사(pref)로 시작하는 문자열의 개수를 세는 역할을 합니다. 코드를 단계별로 설명하면 다음과 같습니다.

1. 클래스 및 함수 선언

class Solution {
public:
    int prefixCount(vector<string>& words, string pref) {
        // ...
    }
};

클래스 Solution: 문제 풀이를 위한 클래스로, LeetCode와 같은 플랫폼에서 자주 사용되는 형식입니다.
prefixCount 함수:
- 입력: 문자열 벡터 words와 접두사 문자열 pref
- 출력: 접두사 pref로 시작하는 문자열의 총 개수 (정수)

2. 함수 내부 동작

int prefixCount(vector<string>& words, string pref) {
    int count = 0;
    for (string& word : words) {
        if (word.find(pref) == 0) {
            count++;  // Found a string with pref as prefix
        }
    }
    return count;
}

변수 count 초기화:
count를 0으로 초기화하여, 조건에 부합하는 문자열의 개수를 누적할 준비를 합니다.
반복문을 이용한 순회:
for (string& word : words) 구문을 사용하여 words 벡터 내의 모든 문자열을 하나씩 순회합니다.
접두사 검사:
- word.find(pref) 함수는 C++ 표준 라이브러리의 find 메서드로, word 문자열 내에서 pref가 처음 등장하는 위치를 반환합니다.
- 중요: 만약 word의 시작 부분(인덱스 0)에서 pref가 일치한다면, word.find(pref)의 반환 값은 0이 됩니다.
- 조건문 if (word.find(pref) == 0)는, word가 pref를 접두사로 가지고 있을 경우에만 참이 되어 count를 증가시킵니다.
최종 결과 반환:
모든 문자열에 대해 검사한 후, 접두사와 일치하는 문자열의 개수(count)를 반환합니다.

요약

목적: 문자열 벡터 words에서 접두사 pref로 시작하는 문자열의 개수를 계산합니다.
방법: 각 문자열에 대해 C++의 find 메서드를 사용하여 접두사가 문자열의 시작 위치(인덱스 0)에 있는지 확인하고, 해당되는 경우 카운트를 증가시킵니다.
결과: 조건을 만족하는 문자열의 총 개수를 반환합니다.

이와 같이, 코드의 간결한 작성 방식은 find 함수를 활용하여 직접 문자열을 비교하는 것보다 훨씬 직관적으로 접두사 여부를 판단할 수 있도록 해줍니다.

Approach 3: Trie

49ms, 71.13MB
Complexity
- Let $n$ be the total number of strings in the input array words, $l$ be the maximum length any string in words and $m$ be the length of the prefix string pref.
- Time Complexity: $O(n \cdot l + m)$
- Space Complexity: $O(n \cdot l)$

class Solution {
public:
    int prefixCount(vector<string>& words, string pref) {
        Trie trie;

        // Add all words to trie
        for (string& word : words) {
            trie.addWord(word);
        }
        return trie.countPrefix(pref);
    }

private:
    class Trie {
        // Node class represents each character in Trie
        struct Node {
            // Links to child nodes
            vector<Node*> links;
            // Number of strings having prefix till this node
            int count;

            Node() : links(26, nullptr), count(0) {}
        };

        Node* root;

    public:
        Trie() { root = new Node(); }

        // Add word to trie and update prefix counts
        void addWord(string& word) {
            Node* curr = root;
            for (char c : word) {
                if (curr->links[c - 'a'] == nullptr) {
                    curr->links[c - 'a'] = new Node();
                }
                curr = curr->links[c - 'a'];
                curr->count++;  // Increment count for this prefix
            }
        }

        // Return count of strings having pref as prefix
        int countPrefix(string& pref) {
            Node* curr = root;
            for (char c : pref) {
                if (curr->links[c - 'a'] == nullptr) {
                    return 0;  // Prefix not found
                }
                curr = curr->links[c - 'a'];
            }
            return curr->count;  // Return count at last node
        }
    };
};

GPT (o3-mini-high)

이 코드는 Trie(트라이) 자료구조를 사용하여 주어진 단어 목록(words)에서 특정 접두사(pref)로 시작하는 단어의 개수를 효율적으로 계산하는 방법을 보여줍니다. 각 단계별로 코드를 살펴보겠습니다.

전체 구조

클래스 Solution
LeetCode 등의 문제 풀이 환경에서 사용되는 표준 클래스입니다.
- prefixCount 함수는 주어진 단어들을 Trie에 추가한 후, 특정 접두사를 가지는 단어의 개수를 Trie에서 조회합니다.
내부 클래스 Trie
문자열들을 저장하고, 접두사 관련 정보를 빠르게 검색하기 위한 Trie 자료구조를 구현합니다.

`prefixCount` 함수

int prefixCount(vector<string>& words, string pref) {
    Trie trie;

    // Add all words to trie
    for (string& word : words) {
        trie.addWord(word);
    }
    return trie.countPrefix(pref);
}

Trie 객체 생성
- Trie trie;를 통해 Trie의 루트 노드를 생성합니다.
단어 추가
- for (string& word : words) 반복문을 통해 words 벡터의 모든 단어를 순회하며, 각 단어를 Trie에 추가합니다.
- 각 단어는 trie.addWord(word);를 호출하여 Trie에 삽입됩니다.
접두사 개수 조회
- trie.countPrefix(pref);를 호출하여, Trie에서 주어진 접두사 pref로 시작하는 단어의 개수를 반환합니다.

Trie 자료구조 내부

Node 구조체

struct Node {
    // 각 알파벳(26개)에 대한 자식 노드 포인터 (a~z)
    vector<Node*> links;
    // 현재 노드까지의 경로를 접두사로 가지는 단어의 개수
    int count;

    Node() : links(26, nullptr), count(0) {}
};

links 벡터:
26개의 원소를 가지며, 각 원소는 해당 알파벳(‘a’부터 ‘z’)에 대응하는 자식 노드에 대한 포인터입니다.
count 변수:
이 노드에 도달하는 경로(즉, 해당 접두사)를 가진 단어들의 수를 저장합니다. 단어를 추가할 때마다 해당 경로를 거치는 모든 노드에서 count가 증가합니다.

Trie 클래스

class Trie {
    Node* root;

public:
    Trie() { root = new Node(); }

root:
Trie의 시작점이며, 빈 문자열에 해당하는 노드입니다.

`addWord` 함수

void addWord(string& word) {
    Node* curr = root;
    for (char c : word) {
        if (curr->links[c - 'a'] == nullptr) {
            curr->links[c - 'a'] = new Node();
        }
        curr = curr->links[c - 'a'];
        curr->count++;  // 이 노드까지 도달하는 단어의 수를 증가시킴
    }
}

동작 과정:
1. 루트부터 시작: curr 포인터를 루트 노드로 초기화합니다.
2. 문자 단위 삽입:
  - 주어진 word의 각 문자 c에 대해,
  - 해당 문자가 존재하지 않으면 새로운 노드를 생성합니다.
  - curr를 해당 문자에 해당하는 자식 노드로 이동합니다.
3. 카운트 증가:
  - 각 노드를 거칠 때마다 curr->count를 증가시켜, 이 경로를 접두사로 가지는 단어가 하나 더 추가되었음을 기록합니다.

`countPrefix` 함수

int countPrefix(string& pref) {
    Node* curr = root;
    for (char c : pref) {
        if (curr->links[c - 'a'] == nullptr) {
            return 0;  // 해당 접두사를 가진 단어가 없음
        }
        curr = curr->links[c - 'a'];
    }
    return curr->count;  // 접두사의 마지막 문자까지 도달했을 때, 해당 노드의 count 반환
}

동작 과정:
1. 루트부터 시작: curr 포인터를 루트 노드로 초기화합니다.
2. 접두사 따라 이동:
  - 주어진 pref의 각 문자에 대해, 해당 문자를 자식 노드에서 찾습니다.
  - 만약 어떤 문자를 찾을 수 없으면, 해당 접두사를 가진 단어가 없으므로 0을 반환합니다.
3. 카운트 반환:
  - 접두사의 모든 문자를 성공적으로 찾았다면, 마지막 노드의 count 값은 그 접두사를 가진 단어들의 총 개수입니다.

요약

Trie 사용의 이점:
모든 단어를 Trie에 추가하면, 접두사 검색이 매우 효율적으로 이루어집니다. 접두사 관련 정보를 각 노드에 저장하여, 주어진 접두사에 해당하는 단어 개수를 빠르게 조회할 수 있습니다.
전체 과정:
1. 모든 단어를 Trie에 삽입하면서, 각 경로(접두사)에 대한 단어의 개수를 기록합니다.
2. pref 접두사를 따라 Trie를 탐색하고, 마지막 노드에서 저장된 count를 반환하여 해당 접두사를 가진 단어의 총 개수를 구합니다.

이와 같이, 이 코드는 Trie 자료구조를 활용해 접두사 검색 문제를 효율적으로 해결하는 방법을 보여줍니다.

2185. Counting Words With a Given Prefix

내 코드

Solution

Approach 1: Brute Force

GPT (o3-mini-high)

1. prefixCount 함수

2. hasPrefix 함수

전체 동작 요약

Approach 2: Built-In Methods

C++

GPT (o3-mini-high)

1. 클래스 및 함수 선언

2. 함수 내부 동작

요약

Approach 3: Trie

GPT (o3-mini-high)

전체 구조

prefixCount 함수

Trie 자료구조 내부

Node 구조체

Trie 클래스

addWord 함수

countPrefix 함수

요약

1. `prefixCount` 함수

2. `hasPrefix` 함수

`prefixCount` 함수

`addWord` 함수

`countPrefix` 함수