문제 링크

내 코드

그냥 Brute Force로 다 확인.

0ms, 8.22MB

class Solution {
public:
    int isPrefixOfWord(string sentence, string searchWord) {
        istringstream iss(sentence);

        string tmp;
        int index{1};
        while(getline(iss, tmp, ' ')) {
            if(tmp.find(searchWord) == 0) { // Return the index of the word in sentence (1-indexed) where searchWord is a prefix of this word.
                return index;
            }
            ++index;
        }
        return -1;
    }
};

Solution

Approach 1: Brute Force

• 0ms, 8.41MB
• Complexity
  • Let $n$ be the size of the input string sentence, $m$ be the size of the input string searchWord, $k$ be the average length of words in sentence, and $w$ be the total number of words in sentence such that $w \cdot k=n$.
  • Time Complexity: $O(n + w \cdot m)$
  • Space Complexity: $O(n)$

class Solution {
public:
    int isPrefixOfWord(string sentence, string searchWord) {
        // List to store the words from the sentence
        vector<string> wordsList;
        // String to build the current word
        string currentWord;

        // Iterate through each character in the sentence
        for (char character : sentence) {
            if (character != ' ') {
                // Append the character to the current word
                currentWord += character;
            } else {
                // If we encounter a space, add the current word to the list
                if (!currentWord.empty()) {
                    wordsList.push_back(currentWord);
                    currentWord = "";  // Reset the string
                }
            }
        }
        // Add the last word if the sentence doesn't end with a space
        if (!currentWord.empty()) {
            wordsList.push_back(currentWord);
        }

        // Iterate through the list of words to find the prefix match
        for (int wordIndex = 0; wordIndex < wordsList.size(); ++wordIndex) {
            if (wordsList[wordIndex].length() >= searchWord.length()) {
                bool isMatch = true;
                for (int charIndex = 0; charIndex < searchWord.length();
                     ++charIndex) {
                    if (wordsList[wordIndex][charIndex] !=
                        searchWord[charIndex]) {
                        isMatch = false;
                        break;
                    }
                }
                if (isMatch) {
                    return wordIndex + 1;  // Return 1-based index
                }
            }
        }
        return -1;  // Return -1 if no match is found
    }
};

Approach 2: Two Pointer

• 0ms, 7.95MB
• Complexity
  • Let $n$ be the size of the input string sentence, and $m$ be the size of the input string searchWord.
  • Time Complexity: $O(n + w \cdot m)$
  • Space Complexity: $O(1)$

class Solution {
public:
    int isPrefixOfWord(string sentence, string searchWord) {
        // Initialize the word position counter
        int currentWordPosition = 1;
        // Initialize the current index in the sentence
        int currentIndex = 0;
        // Get the length of the sentence
        int sentenceLength = sentence.length();

        // Loop through the sentence
        while (currentIndex < sentenceLength) {
            // Skip leading spaces
            while (currentIndex < sentenceLength &&
                   sentence[currentIndex] == ' ') {
                currentIndex++;
                currentWordPosition++;
            }

            // Check if the current word starts with searchWord
            int matchCount = 0;
            while (currentIndex < sentenceLength &&
                   matchCount < searchWord.length() &&
                   sentence[currentIndex] == searchWord[matchCount]) {
                currentIndex++;
                matchCount++;
            }

            // If the entire searchWord matches, return the current word
            // position
            if (matchCount == searchWord.length()) {
                return currentWordPosition;
            }

            // Move to the end of the current word
            while (currentIndex < sentenceLength &&
                   sentence[currentIndex] != ' ') {
                currentIndex++;
            }
        }
        // If no match is found, return -1
        return -1;
    }
};

Approach 3: Using Built-In Function

For C++ Users

In C++, the istringstream class from the <sstream> library processes strings efficiently. It treats a string as a stream and extracts words using the >> operator. This avoids manual string splitting and space handling. The complexity of extracting words is $O(n)$, where n is the string length. To check if a word starts with a prefix, the compare function is used, which operates in $O(k)$, where k is the prefix length.

• 0ms, 13.38MB
• Complexity
  • Let $n$ be the size of the input string sentence, $m$ be the size of the input string searchWord, $k$ be the average length of words in sentence, and $w$ be the total number of words in sentence such that $w \cdot k=n$.
  • Time Complexity: $O(n + w \cdot m)$
  • Space Complexity: $O(n)$
    • In C++, the sort() function is implemented as a hybrid of Quick Sort, Heap Sort, and Insertion Sort, with a worst-case space complexity of $O(\log n)$.

class Solution {
public:
    int isPrefixOfWord(string sentence, string searchWord) {
        // Initialize a string stream to read words from the sentence
        istringstream sentenceStream(sentence);
        string currentWord;

        // Start counting word positions from 1
        int wordPosition = 1;

        // Loop through each word in the sentence
        while (sentenceStream >> currentWord) {
            // Check if the current word is long enough to contain the
            // searchWord as a prefix and if the prefix matches the searchWord
            if (currentWord.length() >= searchWord.length() &&
                currentWord.compare(0, searchWord.length(), searchWord) == 0) {
                // If a match is found, return the current word position
                return wordPosition;
            }
            // Move to the next word position
            wordPosition++;
        }
        // If no match is found, return -1
        return -1;
    }
};