Preface explains

Algorithm learning, daily brush record.

Subject to connect

Invert a vowel in a string

The subject content

Given a string s, reverse only all vowels in the string and return the resulting string.

Vowels include ‘a’, ‘e’, ‘I’, ‘o’, and ‘u’, and may appear in both upper and lower case.

Example 1:

Enter: s = “hello”

Output: “holle”

Example 2:

Enter: s = “leetcode”

Output: “leotcede”

Tip:

1 <= S. length <= 3 * 10^5 s consists of printable ASCII characters

Method 1

Use the two-pointer method to traverse characters from both sides of the string, inverting assignments to the array if vowels appear on either side, or directly to the array otherwise.

However, pay attention to the movement and stop of the left and right Pointers. Use isLeft and isRight to check whether the left and right Pointers are all vowels. Only when the left and right Pointers are all vowels, exchange the two characters.

Since it is not clear whether the left pointer comes first or the right pointer first, we judge it three times, first the left pointer, then the right pointer, and then the left pointer.

The code is as follows:

Class Solution {public String reverseVowels(String s) {class Solution {public String reverseVowels(String s) {public String reverseVowels(String s) { If (s.length() == 1) {// If the string length is 1, return s; Char [] cs = new char[s.length()]; char[] cs = new char[s.length()]; Boolean isLeft = false; Boolean isRight = false; Int left = 0; Int right = s.length() -1; int right = s.length() -1; While (left < right) {if (isVowels(s.charat (left))) {// If (isVowels(s.charat (left))) { IsLeft = true; If (isRight | | left > = right) {/ / if the logo is also true of right pointer or pointer left pointer is equal to the right, then right pointer subscript characters assignment to the position of the left pointer subscript of an array of characters, Cs [left] = s.char (right); cs[left] = s.char (right); cs[right] = s.charAt(left); }} else {// If the left pointer subscript is not a vowel, the identifier is false, the character is directly assigned to the character array, the left pointer increment 1 isLeft = false; cs[left] = s.charAt(left); ++left; } if (isVowels(s.charat (right))) {// If the right pointer subscript character is a vowel, the mark is true isRight = true; If (isLeft | | left > = right) {/ / if the logo is also true of left or right pointer is equal to the left, the left pointer subscript characters assigned to the position of the pointer right subscript of an array of characters, Cs [right] = s.char (left); cs[right] = s.char (left); cs[left] = s.charAt(right); }} else {// If the character is not a vowel, the identifier is false, and the character is directly assigned to the character array, the right pointer is reduced by 1 isRight = false; cs[right] = s.charAt(right); --right; } // Check whether the left subscript is a vowel, because the right subscript is a vowel, if the right subscript is a vowel, but the left subscript is a vowel, the program cannot run back, If (isVowels(s.charat (left))) {// If (isVowels(s.charat (left))) {// If (isVowels(s.charat (left)) = true; If (isRight | | left > = right) {/ / if the logo is also true of right pointer or pointer left pointer is equal to the right, then right pointer subscript characters assignment to the position of the left pointer subscript of an array of characters, Cs [left] = s.char (right); cs[left] = s.char (right); cs[right] = s.charAt(left); }} if (isLeft &&isright) {// If (isLeft &&isright) {// If (isLeft &&isright) {// If (isLeft &&isright) {// If (isLeft &&isright) {// If (isLeft &&isright) {// If (isLeft &&isright) { isRight = false; ++left; --right; } if (left == right) {// If (left == right) {// If (left == right) {// If (left == right) {// If (left == right) {// If (left == right) {// If (left == right) {// If (left == right) {// If (left == right) {// If (left == right) {// If (left == right) {// If (left == right) { Cs [left] = s.charat (left); Return new String(cs); } / / whether the current character for vowels private Boolean isVowels (char) c {return 'a' = = c | | 'e' = = c | | 'I = = c | |' o '= = c | |' u '= = c | |  'A' == c || 'E' == c || 'I' == c || 'O' == c || 'U' == c; }}Copy the code

Submit the code to run, the running results are as follows:

The execution time was 3ms, the time beat 81.95% of users, the memory consumption was 38.3MB, and the space beat 87.70% of users.

Method 2

However, method 1 is complicated and confusing, which is difficult to understand and may not be understood, so it is not recommended. Method 2 is optimized and adjusted to become logical and clear.

Method 2 also uses the double-pointer method, traversing the characters from both sides of the character array until vowels appear or the array boundary is exceeded. If two vowels appear when the left pointer is smaller than the right pointer, the two vowels in the character array are swapped.

Step 1

We convert the string S into the character array arr.

Define the left pointer left, starting at 0, to the left of the character array arr.

Define the right pointer right, starting at the right of arr and starting with the last subscript of arr.

Step 2

The double pointer iterates through the array arr until left is greater than or equal to right.

Step 3

Loop:

If left does not exceed the bounds of the array and the character is not a vowel, then left moves incremented by 1 until the character is a vowel.

If the right pointer right does not exceed the bounds of the array and the position of the pointer is not a vowel, then the right pointer right moves minus 1 until the character beyond the bounds of the array or the position of the pointer is a vowel, ending the loop.

After the above two internal loops, either the left pointer left is greater than or equal to the right pointer right, or the characters in the left and right positions are vowels.

If the left pointer is less than the right pointer, then all the characters in the left and right positions are vowels. Swap these two vowels, and the left pointer increases by 1, and the right pointer decreases by 1.

Step 4

At the end of the loop, the character array arr is converted to a string and the result is returned.

The code is as follows:

Class Solution {public String reverseVowels(String s) {class Solution {public String reverseVowels(String s) {class Solution {public String reverseVowels(String s) { Char [] arr = s.tochararray (); char[] arr = s.tochararray (); Int left = 0; int left = 0; Int right = s.length() -1; int right = s.length() -1; // Double pointer traverses the array of characters, Loop until the left pointer is greater than or equal to the right pointer while (left < right) {while (left < s.length() &&isnotvowel (arr[left])) {// If the left pointer does not exceed the bounds of the array and the character at the position is not a vowel, then the left pointer moves incremented by 1 until the character at the position is a vowel. } while (right > 0 && isNotVowel(arr[right]) {if (right > 0 &&isnotVowel (arr[right])) {if (right > 0 &&isnotVowel (arr[right])) {if (right > 0 &&isnotVowel (arr[right])) {if (right > 0 &&isnotVowel (arr[right])) {if (right > 0 &&isnotVowel (arr[right])) { End loop --right; If (left < right) {// If (left < right) {// If (left < right) {// If (left < right) { Swap the two vowels swap(arr, left, right); // add 1 ++left; // right pointer minus 1 --right; Return new String(arr); } private Boolean isNotVowel(char c) {return 'a'! = c && 'e' ! = c && 'i' ! = c && 'o' ! = c && 'u' ! = c && 'A' ! = c && 'E' ! = c && 'I' ! = c && 'O' ! = c && 'U' ! = c; } private void swap(char[] arr, int left, int right) {char temp = arr[left]; arr[left] = arr[right]; arr[right] = temp; }}Copy the code

Submit the code to run, the running results are as follows:

The execution time was 2ms, beating 99.77% of users in time, 38.4MB in memory consumption, and beating 76.83% in space.

The original link

Reverse a vowel in a string