algoadvance

Leetcode 824. Goat Latin

Problem Statement

The 824. Goat Latin problem requires you to transform a given sentence as per the following rules:

  1. If a word begins with a vowel (a, e, i, o, or u), append “ma” to the end of the word. For example, the word “apple” becomes “applema”.
  2. If a word begins with a consonant (i.e., not a vowel), remove the first letter and append it to the end, then add “ma”. For example, the word “goat” becomes “oatgma”.
  3. Add one letter ‘a’ to the end of each word per its word index in the sentence, starting with 1. For example, the first word gets one ‘a’ added to the end, the second word gets two ‘a’s, and so on.

Given an input sentence, apply these transformations to each word and return the resultant sentence.

Clarifying Questions

  1. Input constraints:
    • Can we assume the input is always a valid sentence with words separated by single spaces and no leading or trailing spaces?

    Yes, assume the input is always a valid sentence without leading or trailing spaces.

  2. Character set:
    • Are the words composed only of lowercase and uppercase English letters?

    Yes, the words are composed of only lowercase and uppercase English letters.

  3. Case sensitivity:
    • Is the transformation case-insensitive?

    No, the transformation should respect the original case of the letters.

Strategy

  1. Split Sentence: Split the input sentence into words.
  2. Transform Each Word: For each word, apply the transformation rules.
    • If the word starts with a vowel, append “ma”.
    • If the word starts with a consonant, move the first letter to the end, then append “ma”.
    • Append ‘a’s according to the word’s position in the sentence.
  3. Join Transformed Words: Join the transformed words back into a sentence.

Code

Here’s the C++ solution to transform a sentence into “Goat Latin”:

#include <iostream>
#include <sstream>
#include <vector>

using namespace std;

class Solution {
public:
    string toGoatLatin(string S) {
        // Helper function to check if a character is a vowel
        auto is_vowel = [](char c) -> bool {
            c = tolower(c);
            return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
        };
        
        istringstream iss(S);
        string word;
        vector<string> words;
        int index = 0;
        
        while (iss >> word) {
            index++;
            if (is_vowel(word[0])) {
                word += "ma";
            } else {
                word = word.substr(1) + word[0] + "ma";
            }
            word += string(index, 'a');
            words.push_back(word);
        }
        
        string result;
        for (int i = 0; i < words.size(); i++) {
            if (i > 0) result += " ";
            result += words[i];
        }
        
        return result;
    }
};

int main() {
    Solution solution;
    string sentence = "I speak Goat Latin";
    string transformed = solution.toGoatLatin(sentence);
    cout << transformed << endl;
    return 0;
}

Time Complexity

Overall, the time complexity is O(n), where n is the total length of the input sentence.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI