“Offer comes, ask friends to take it! I am participating in the 2022 Spring Recruit Punch card campaign. Click here for more details.”

📢 preface

🚀 Algorithm 🚀
  • 🌲 punch in an algorithm every day, which is not only a learning process, but also a sharing process 😜
  • 🌲 tip: the programming languages used in this column are C# and Java
  • 🌲 to maintain a state of learning every day, let us work together to become a god of algorithms 🧐!
  • 🌲 today is the 99th day 🎈!
🚀 Algorithm 🚀

🌲 Latin for goat

Given a sentence S that separates words by Spaces. Each word contains only upper or lower case letters.

We’ll convert the sentence to “Goat Latin” (a fictional language similar to Pig Latin).

The rules for Latin goat are as follows:

  • If the word begins with a vowel sound (a, e, I, o, u), add “ma” to the end of the word.

For example, the word “apple” becomes “applema”.

  • If the word begins with a consonant (that is, a non-vowel), remove the first character and place it at the end, then add “ma”.

For example, the word “goat” became “oatgma”.

  • According to the index of the word in the sentence, add the same number of letters’ A ‘at the end of the word as the index, starting at 1.

For example, add “A” after the first word, “aa” after the second word, and so on.

Returns the sentence after converting S to Goat Latin.

Example 1:

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

Example 2:

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

Tip:

  • The S contains only uppercase and lowercase letters and Spaces. There is one and only one space between words.
  • 1 <= S.length <= 150.

🌻C# method: traverse

Iterate through the number group, and then make a conditional judgment

If it is a vowel, it is added, if it is a consonant, it is shifted and reprocessed

Code:

public class Solution {
    public string ToGoatLatin(string S) {
              string[] arr = S.Split("");
              char[] yuan = new char[] { 'a'.'e'.'i'.'o'.'u' ,'A'.'E'.'I'.'O'.'U' };
            StringBuilder str = new StringBuilder();
            string res = "";
            for (int i = 0; i < arr.Length; i++)
            {
                if(res! ="")
                {
                    res += "";
                }
                       str.Clear();
                str.Append(arr[i]);
                if (yuan.Contains(str[0]))
                {
                    str.Append("ma");
                }
                else
                {
                    str.Append(str[0]);
                    str.Remove(0.1);
                    str.Append("ma");
                }
                for (int j = 0; j <= i; j++)
                {
                    str.Append("a");
                }
                res += str.ToString();
            }
            returnres; }}Copy the code

The execution result

By execution time:124Ms, in all CBeat 100.00% of users in submissionMemory consumption:45.9MB, in all C# beat 43.90% of users in submission
Copy the code

🌻Java method: string

For each word in the sentence, if it is a vowel, it does not change. If it’s a consonant, rotate the word (word[1:] + word[:1] in Python, word. Substring (1) + word. Substring (0, 1) in Java.

Then, we add “ma” and the desired number of “a” and a space.

Code:

class Solution {
    public String toGoatLatin(String S) {
        Set<Character> vowel = new HashSet();
        for (char c: new char[] {'a'.'e'.'i'.'o'.'u'.'A'.'E'.'I'.'O'.'U'})
            vowel.add(c);

        int t = 1;
        StringBuilder ans = new StringBuilder();
        for (String word: S.split("")) {
            char first = word.charAt(0);
            if (vowel.contains(first)) {
                ans.append(word);
            } else {
                ans.append(word.substring(1));
                ans.append(word.substring(0.1));
            }
            ans.append("ma");
            for (int i = 0; i < t; i++)
                ans.append("a");
            t++;
            ans.append("");
        }

        ans.deleteCharAt(ans.length() - 1);
        returnans.toString(); }}Copy the code

The execution result

By execution time:2Ms, beat out all Java commits87.98% user memory consumption:38.3MB, beat out all Java commits94.50% of the userCopy the code

Complexity analysis

Time complexity: O(N^2) space complexity: O(N^2) 
Copy the code

💬 summary

  • Today is the ninety-ninth day of the buckle algorithm.
  • The article USES theC# andJavaTwo programming languages to solve the problem
  • Some methods are also written by the god of reference force buckle, and they are also shared while learning, thanks again to the algorithm masters
  • That’s the end of today’s algorithm sharing, see you tomorrow!