Java&C++题解与拓展——leetcode824.山羊拉丁文【么的新知识】

• 题目要求
• 思路：模拟
• • Java
  • C++
  • • 字符串构造
• 总结

简单、立即推、模拟……

就是找到每一个单词，然后根据是否是元音开头判断要不要改变一下顺序，之后添加末尾的maaaa……

class Solution {
    public String toGoatLatin(String sentence) {
        int n = sentence.length();
        String a = "a";
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < n; ) {
            int j = i;
            while(j < n && sentence.charAt(j) != ' ') // 定位当前完整单词
                j++;
            if("aeiouAEIOU".indexOf(sentence.charAt(i)) >= 0) // 元音开头
                sb.append(sentence.substring(i, j));
            else
                sb.append(sentence.substring(i + 1, j)).append(sentence.charAt(i));
            sb.append("ma").append(a); // 添加尾巴
            a += "a";
            i = j + 1;
            if(i < n)
                sb.append(" ");
        }
        return sb.toString();
    }
}

• 时间复杂度： O ( n ) O(n) O(n)
• 空间复杂度： O ( n ) O(n) O(n)

class Solution {
public:
    string toGoatLatin(string sentence) {
        int n = sentence.length();
        string vowel = "aeiouAEIOU";
        string a = "a";
        string res = "";
        for(int i = 0; i < n; ) {
            int j = i;
            while(j < n && sentence[j] != ' ') // 定位当前完整单词
                j++;
            if(vowel.find(sentence[i]) != string::npos) // 元音开头
                res += sentence.substr(i, j - i);
            else
                res += sentence.substr(i + 1, j - i - 1) + sentence[i];
            res += "ma" + a; // 添加尾巴
            a += "a";
            i = j + 1;
            if(i < n)
                res += " ";
        }
        return res;
    }
};

• 时间复杂度： O ( n ) O(n) O(n)
• 空间复杂度： O ( n ) O(n) O(n)

上面构造字符串a时是每次拼接，也可以换用字符串构造函数string(cnt, 'a')，cnt为本次需添加几个 a a a，初值为1。
那两句加尾巴就可以变成：

res += "ma" + string(cnt++, 'a');

模拟模拟，理清思路直接写就完了。

官方题解里说时间复杂度是 O ( n 2 ) O(n^2) O(n2)就很迷惑，不就只遍历了一圈……但他的意思是返回的字符串数量级是 O ( n 2 ) O(n^2) O(n2)的，因为带了一堆小尾巴……这个复杂度是要看返回值的么？？？不是单纯计算？？？

还要好好xiao一下时间复杂度计算相关的内容啊……