Understand the topic

Recently, I have been reading a lot of algorithm problems. I hope I can record the process of algorithm analysis with a small topic. Pig Latin

Pig Latin is a way of altering English Words. The rules are as follows:

  • If a word begins with a consonant, take the first consonant or consonant cluster, move it to the end of the word, and add “ay” to it.

If a word begins with a vowel, just add “way” at the end.

When faced with a problem with less description, the first reaction is that the simpler the problem description, the more hidden conditions there will be. Before you panic, read Wikipedia’s explanation for Pig Latin. I like to look at Wikipedia before reading the topic, so that I can know the background and origin of the topic, so that I can better understand the topic and solve the problem is also interesting. Here’s a simple rule: When a word begins with a consonant, say it ends with a consonant and add ay, for example

  • california → aliforniacay : cMove to the end and adday
  • paragraphs → aragraphspay:pMove to the end and adday
  • glove → oveglay:glMove to the end and adday⚠️ Here are all the consonants until the first vowel is found

Vowels: A, E, I, O, U

When a word begins with a vowel, add “way” (e.g

  • algorithm → algorithmway : aIt’s a vowel so it’s added after the wordway
  • eight → eightway : eIt’s a vowel so it’s added after the wordway

Once the problem is analyzed, we also need to check for any omissions by reading the test cases. Look at the last item:

TranslatePigLatin (” rhythm “) Should return “rhythmay”.

This rule actually satisfies the first case, when the vowel is not found, simply add ay after it

The analysis process

When we are given an algorithm problem, we attack the city in several ways.

  1. There are two kinds of operations on strings:
    1. Traverse by index
    2. Replace, replace in particular does not talk about martial virtue with regular.
  2. From shallow to deep:
    1. Is to come up first according to the given conditions, in accordance with the direction of violence to write pseudo-code
    2. In accordance with the logic to find key cycle factors and optimization means
    3. Try to optimize the

Pseudo code

Write pseudo code first, this part of the code is rough, mainly for sorting out the analysis process

VAR STR VAR vowelLetters = ['a','e',' I ','o','u'] IF STR[0] in vowelLetters return STR + 'way FOR (S, INDEX) in STR IF S in vowelLetters return str.slice (INDEX) + str.slice (0,INDEX) + 'ay' //Copy the code

Now that we have the analysis process we can write JavaScript code

function translatePigLatin(str) {
	// Prepare the required array of vowels
	const vowelLetters = ['a'.'e'.'i'.'o'.'u']
	// Special case: if it begins with a vowel
	if(vowelLetters.includes(str[0])) return `${str}way`	
	
	// Normal condition
	for (let i = 0; i < str.length; i++) {
		if(vowelLetters.includes(str[i])) {
			return `${str.slice(i)}${str.slice(0, i)}ay`}}// There are no vowels
	return `${str}ay`
}

translatePigLatin("consonant");
Copy the code

Review the 👆 code above, which has passed the test, then analyze how to optimize. ${str.slice(I)}${str.slice(0, I)}ay

function translatePigLatin(str) {
	// find the index
	let index = str.split(' ').findIndex(s= > /[aeiou]/.test(s))

	if(the index <0)return `${str}ay`
	if (index === 0)return `${str}way`
	return `${str.slice(index)}${str.slice(0, index)}ay`
}

translatePigLatin("consonant");
Copy the code

The code is simpler and the logic is clearer

Another road

From the point of view of the analysis process, the looping method has been completed, so how should the other path (replace) be implemented? The result of the first method is to use the regular grouping method to switch positions. The idea is to have two groups: the first group is beginning to vowel, and the second group is vowel to end. The two groups were then reversed and suffixed. It is recommended when developing and debugging regexregex101.com/To debug regular expressions

Use the debugger to complete the re: /([^aeiou]*)(\w*)/ explain

  1. Use two parentheses. Divide into two groups
  2. ([^aeiou]*)Indicates that the match is not (^Aeiou 0 to more than one character.
  3. (\w*)The remaining characters are a group

Complete code

function translatePigLatin(str) {
	return str.replace(/([^aeiou]*)(\w*)/.'$2$1ay')
}

translatePigLatin("consonant");
Copy the code

Through testing, the code above 👆 has been included in the other two cases except for the vowel at the beginning. ([^aeiou]*) $1 = ([^aeiou]*) $1 = ([^aeiou]*) $1 = ([^aeiou]*) $1 = ([^aeiou]*) $1 = ([^aeiou]*) $1 = ([^aeiou]*) $1 = ([^aeiou]*) JavaScript String the replace method the second parameter is the String of support function prototype. The replace () – JavaScript | MDN

function translatePigLatin(str) {
	return str.replace(/([^aeiou]*)(\w*)/.(_, p1, p2) = > `${p2}${p1||'w'}ay`)
}

translatePigLatin("consonant");
Copy the code

conclusion

So to summarize the basic formula when you get an algorithm problem

  1. Categorization, that’s the kind of problem, you can basically determine the direction after categorization, so for example, most of the tree problems are going to use recursion, so if you want to train recursion deliberately, you can train recursion under tree groups.
  2. Analyze the topic logic first, write out the pseudo-code of the logic in a simple and crude way, and then break through the optimization.
  3. Review whether there is a better solution in other directions.

One final tip: If you want to break through an interview in the short term, swipe LeetCode. Also recommended: www.codewars.com/. Codewars, by contrast, focuses more on current programming language practices than on optimal algorithms, and there are a lot of “surprises” in there. You’ll be impressed by a lot of “dark magic”. Codewars is rumored to have a higher difficulty limit.