824. 山羊拉丁文

题目描述

给你一个由若干单词组成的句子 sentence ，单词间由空格分隔。每个单词仅由大写和小写英文字母组成。

请你将句子转换为 “山羊拉丁文（Goat Latin）”（一种类似于 猪拉丁文 - Pig Latin 的虚构语言）。山羊拉丁文的规则如下：

• 如果单词以元音开头（'a', 'e', 'i', 'o', 'u'），在单词后添加"ma"。
  • 例如，单词 "apple" 变为 "applema" 。
• 如果单词以辅音字母开头（即，非元音字母），移除第一个字符并将它放到末尾，之后再添加"ma"。
  • 例如，单词 "goat" 变为 "oatgma" 。
• 根据单词在句子中的索引，在单词最后添加与索引相同数量的字母'a'，索引从 1 开始。
  • 例如，在第一个单词后添加 "a" ，在第二个单词后添加 "aa" ，以此类推。

返回将 sentence 转换为山羊拉丁文后的句子。

示例 1：

输入：sentence = "I speak Goat Latin"
输出："Imaa peaksmaaa oatGmaaaa atinLmaaaaa"

示例 2：

输入：sentence = "The quick brown fox jumped over the lazy dog"
输出："heTmaa uickqmaaa rownbmaaaa oxfmaaaaa umpedjmaaaaaa overmaaaaaaa hetmaaaaaaaa azylmaaaaaaaaa ogdmaaaaaaaaaa"

提示：

• 1 <= sentence.length <= 150
• sentence 由英文字母和空格组成
• sentence 不含前导或尾随空格
• sentence 中的所有单词由单个空格分隔

解法

方法一：找到每一个单词 + 模拟

思路与算法

我们可以对给定的字符串 \(\textit{sentence}\) 进行一次遍历，找出其中的每一个单词，并根据题目的要求进行操作。

在寻找单词时，我们可以使用语言自带的\(\texttt{split()}\) 函数，将空格作为分割字符，得到所有的单词。为了节省空间，我们也可以直接进行遍历：每当我们遍历到一个空格或者到达 \(\textit{sentence}\) 的末尾时，我们就找到了一个单词。

当我们得到一个单词 \(w\) 后，我们首先需要判断 \(w\) 的首字母是否为元音字母。我们可以使用一个哈希集合 \(\textit{vowels}\) 存储所有的元音字母 \(\text{aeiouAEIOU}\)，这样只需要判断 \(w\) 的首字母是否在 \(\textit{vowels}\) 中。如果是元音字母，那么单词本身保持不变；如果是辅音字母，那么需要首字母移到末尾，这里使用语言自带的字符串切片函数即可。在这之后，我们需要在末尾添加 \(\text{m}\) 以及若干个 \(\text{a}\)，因此可以使用一个变量 \(\textit{cnt}\) 记录需要添加的 \(\text{a}\) 的个数，它的初始值为 \(1\)，每当我们得到一个单词，就将它的值增加 \(1\)。

复杂度分析

时间复杂度：\(O(n^2)\)，其中 \(n\) 是字符串 \(\textit{sentence}\) 的长度。虽然我们对字符串只进行了常数次遍历，但是返回的字符串长度的数量级是 \(O(n^2)\)的。

空间复杂度：\(O(n^2)\) 或 \(O(n)\)，取决于使用的语言的字符串是否可修改。如果可以修改，我们只需要 \(O(n)\) 的空间临时存储字符串切片；如果不可以修改，我们需要 \(O(n^2)\) 的空间临时存储所有单词修改后的结果。注意这里不计入返回字符串使用的空间。

Python3

class Solution:
    def toGoatLatin(self, sentence: str) -> str:
        vowels = {"a", "e", "i", "o", "u", "A", "E", "I", "O", "U"}

        n = len(sentence)
        i, cnt = 0, 1
        words = list()

        while i < n:
            j = i
            while j < n and sentence[j] != " ":
                j += 1
            
            cnt += 1
            if sentence[i] in vowels:
                words.append(sentence[i:j] + "m" + "a" * cnt)
            else:
                words.append(sentence[i+1:j] + sentence[i] + "m" + "a" * cnt)
            
            i = j + 1
        
        return " ".join(words)

class Solution:
    def toGoatLatin(self, sentence: str) -> str:
        ans = []
        for i, word in enumerate(sentence.split()):
            if word.lower()[0] not in ['a', 'e', 'i', 'o', 'u']:
                word = word[1:] + word[0]
            word += 'ma'
            word += 'a' * (i + 1)
            ans.append(word)
        return ' '.join(ans)

C++

class Solution {
public:
    string toGoatLatin(string sentence) {
        unordered_set<char> vowels = {'a','e','i','o','u','A','E','I','O','U'};
        int n = sentence.size();
        int i = 0,cnt =1;
        string ans;

        while(i<n){
            int j = i;
            while(j <n && sentence[j] !=' ')
                ++j;
            
            ++cnt;
            if(cnt !=2)
                ans += ' ';
            if(vowels.count(sentence[i])){
                ans +=sentence.substr(i,j-i) + 'm' +string(cnt,'a');
            }
            else{
                ans +=sentence.substr(i+1,j-i-1) + sentence[i] + 'm' + string(cnt,'a');
            }
            i = j+1;
        }
        return ans;
    }
};