Problem Explanation

We are given a sentence that is composed of words separated by spaces. Each word consists of lowercase and uppercase letters only. The problem statement asks us to convert the given sentence into a fictional language called "Goat Latin".

The rules of Goat Latin are as follows:

1. If a word starts with a vowel (a, e, i, o, or u), append "ma" to the end of the word. For example, the word 'apple' converts to 'applema'.

2. If a word starts with a consonant, remove the first letter and append it to the end, then add "ma". For instance, the word "goat" converts into "oatgma".

3. Lastly, append a letter 'a' to the end of each word per its word index in the sentence, starting with 1. Meaning, the first word will have "a" added to its end, the second word will have "aa" added to its end and so on.

Our task is to return the final sentence that represents the conversion from the original sentence to Goat Latin.

For instance,

• Input: "I speak Goat Latin"
• Output: "Imaa peaksmaaa oatGmaaaa atinLmaaaaa"

Approach

The approach involves scanning each word of the input sentence as follows:

• If a word begins with a vowel, append "ma" to it.
• If a word begins with a consonant, move the first letter to the end and then add "ma".
• Lastly, append "a" to the word as per its position in the sentence.

This is implemented by treating the initial sentence as a stream of words and processing each word according to the Goat Latin language rules.

Solution in Python

1
2python
3class Solution:
4    def toGoatLatin(self, S: str) -> str:
5        vowels = set({'a','A','e','E','i','I','o','O','u','U'})
6        sentence = S.split(' ')
7        N = len(sentence)
8        for i in range(N):
9            # move first letter to end if it's a consonant
10            if sentence[i][0] not in vowels:
11                sentence[i] = sentence[i][1:] + sentence[i][0]
12            # add "ma" to the word
13            sentence[i] = sentence[i] + 'ma'
14            # append 'a's to the word
15            for j in range(i+1):
16                sentence[i] = sentence[i] + 'a'
17        return ' '.join(sentence)

Solution in Java

1
2java
3class Solution {
4    public String toGoatLatin(String S) {
5        Set<Character> vowels = new HashSet<Character>();
6        for (char c : "aeiouAEIOU".toCharArray()) vowels.add(c);
7        String res = "";
8        String[] words = S.split(" ");
9        int index = 1;
10        for (String word : words) {
11            if (index > 1) 
12                res += " ";
13            char firstLetter = word.charAt(0);
14            if (vowels.contains(firstLetter)) {
15                res += word + "ma";
16            } else {
17                res += word.substring(1) + firstLetter + "ma";
18            }
19            for (int j = 0; j < index; j++) {
20                res += "a";
21            }
22            index++;
23        }
24        return res;
25    }
26}

Solution in JavaScript

1
2javascript
3var toGoatLatin = function(S) {
4    const vowels = new Set(['a','e','i','o','u','A','E','I','O','U']);
5    const words = S.split(' ');
6    for (let i = 0; i < words.length; i++) {
7        if (!vowels.has(words[i][0])) {
8            words[i] = words[i].slice(1) + words[i][0];
9        }
10        words[i] += 'ma' + 'a'.repeat(i + 1);
11    }
12    return words.join(' ');
13};

Solution in C++

1
2c++
3class Solution {
4public:
5    string toGoatLatin(string S) {
6        stringstream ss(S);
7        string word;
8        string ans = "";
9        string vowel = "aeiouAEIOU";
10        int i= 1; 
11        while(ss >> word) {
12            if(vowel.find(word[0]) == string::npos)
13                word = word.substr(1) + word[0];
14            word += "ma";
15            for(int j = 0; j < i; j++) word += "a";
16            ans += word + " ";
17            i++;
18        }
19        ans.pop_back();
20        return ans;
21    }
22};

Solution in C#

1
2csharp
3public class Solution {
4    public string ToGoatLatin(string S) {
5        HashSet<char> vowels = new HashSet<char>() { 'a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U' };
6        string[] words = S.Split(' ');
7        for (int i = 0; i < words.Length; i++)
8        {
9            if (!vowels.Contains(words[i][0]))
10                words[i] = words[i].Substring(1) + words[i][0];
11            words[i] += "ma" + new string('a', i + 1);
12        }
13        return string.Join(' ', words);
14    }
15}

In all these solutions, we use a vowel set to check whether the first character of a word is a vowel or a consonant. If it's a vowel, we directly add "ma" to the word. If it's a consonant, we move the first character to the end before adding "ma". We then append as many 'a's as the 1-indexed position of the word in the sentence. At the end, we join all the words to form the final Goat Latin sentence. The same logic is applied in all the languages.# Complexity Analysis

Time complexity: O(n^2), where n is the number of words in the sentence. We are iterating over every word and performing string concatenation operation. In python, string concatenation in a loop has a quadratic time complexity because each time a new string gets created.

Space complexity: O(n^2), where n is the number of words in the sentence. We are storing output string that grows in size with the number of words and also the size of the word itself. This leads to quadratic space complexity.

Conclusion

The outlined solutions for converting a sentence to "Goat Latin" work across a range of common programming languages and use similar rules and principles. Despite each language having its different syntax and peculiarities, the core logic remains the same. This problem gives us a good understanding of string manipulation and string concatenation in python, java, javascript, C++, and C#. It also signals how checking the occurrence of an element in a data structure like a set is done. It's also an interesting example of a problem that may seem complex on the surface but is fundamentally simple when approached with the right logic and understanding of the problem domain. As always, understanding the problem and carefully planning out your solution is key to handling such problems effectively.