Goat Latin

Question

A sentence S is given, composed of words separated by spaces. Each word consists of lowercase and uppercase letters only.

We would like to convert the sentence to "Goat Latin" (a made-up language similar to Pig Latin.)

The rules of Goat Latin are as follows:

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'.

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".

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 "a" added to the end, the second word gets "aa"added to the end and so on.

Return the final sentence representing the conversion from S to Goat Latin.

Example 1:

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

Example 2:

Input: "The quick brown fox jumped over the lazy dog" Output: "heTmaa uickqmaaa rownbmaaaa oxfmaaaaa umpedjmaaaaaa overmaaaaaaa hetmaaaaaaaa azylmaaaaaaaaa ogdmaaaaaaaaaa"

Note:

S contains only uppercase, lowercase and spaces. Exactly one space between each word.

1 <= S.length <= 150.

Approach 1: Direct Solution

Intuition and Algorithm

Here, we use a direct idea to the problem.

class Solution(object):
    def toGoatLatin(self, S):
        out = []
        for i, w in enumerate(S.split(' ')): # 返回序号i和第i个单词
            if w[0] not in list('aeiouAEIOU'): # Smart!
                w = w[1:] + w[0]
            out.append(w + 'ma' + 'a'*(i+1))
        return ' '.join(out)


def main():
    S="I speak Goat Latin"
    solution=Solution().toGoatLatin(S)
    print(solution)


if __name__ == "__main__":
    main()

Complexity Analysis

Time Complexity: O(n), where n is the total words of S.
Space Complexity: O(1).
Runtime: 28 ms, faster than 16.77% of Python online submissions for Goat Latin.
Memory Usage: 11.7 MB, less than 85.71% of Python online submissions for Goat Latin.

Approach 2: Subfunction

Intuition

We apply the steps given in the problem in a straightforward manner. The difficulty lies in the implementation.

Algorithm

For each word in the sentence split, if it is a vowel we consider the word, otherwise we consider the rotation of the word (either word[1:] + word[:1] in Python, otherwise word.substring(1) + word.substring(0, 1)in Java).

Afterwards, we add "ma", the desired number of "a"'s, and a space character.

class Solution(object):
    def toGoatLatin(self, S):
        def convert(word):
            if word[0] not in 'aeiouAEIOU':
                word = word[1:] + word[:1]
            return word + 'ma'

        return " ".join(convert(word) + 'a' * i
                        for i, word in enumerate(S.split(), 1))

Complexity Analysis

Time Complexity: O(), where N is the length of S. This represents the complexity of rotating the word and adding extra "a" characters.
Space Complexity: O(), the space added to the answer by adding extra "a" characters.
Runtime: 20 ms, faster than 71.17% of Python online submissions for Goat Latin.
Memory Usage: 11.8 MB, less than 45.09% of Python online submissions for Goat Latin.

Next challenges:

Txing

Q824 Goat Latin

Goat Latin

Question

Approach 1: Direct Solution

Approach 2: Subfunction