This is the 19th day of my participation in the August Wenwen Challenge.More challenges in August

Topic describes

This is 345. Reverse the vowel in the string on LeetCode, difficulty is easy.

Tag: “dual pointer”, “analog”

Write a function that takes a string as input and inverts the vowels in that string.

Example 1:

Input: "hello" Output: "holle"Copy the code

Example 2:

Input: "leetcode" Output: "leotcede"Copy the code

Tip:

  • Vowels do not contain the letter “y”.

Double pointer

A naive approach is to use a “double pointer” to scan back and forth, swapping and moving to the next place when the left and right Pointers are both vowels.

Because vowels are relatively fixed, we can store them using containers and use the static modifier to ensure that the creation of the entire container and the filling of vowels only happens once in all of the test samples.

We expect the container to be able to determine vowels within the complexity of O(1)O(1)O(1), either using the language’s own hash class container (P2P2P2 code) or using array emulation (P1P1P1 code).

Some details: Since the title doesn’t say that strings contain only letters, we need to subtract the minimum ASCII value (null character) from the current character instead of ‘A’ when using array simulation hash tables.

Code:

class Solution {
    static boolean[] hash = new boolean[128];
    static char[] vowels = new char[] {'a'.'e'.'i'.'o'.'u'};
    static {
        for (char c : vowels) {
            hash[c - ' '] = hash[Character.toUpperCase(c) - ' '] = true; }}public String reverseVowels(String s) {
        char[] cs = s.toCharArray();
        int n = s.length();
        int l = 0, r = n - 1;
        while (l < r) {
            if (hash[cs[l] - ' '] && hash[cs[r] - ' ']) {
                swap(cs, l++, r--);
            } else {
                if(! hash[cs[l] -' ']) l++;
                if(! hash[cs[r] -' ']) r--; }}return String.valueOf(cs);
    }
    void swap(char[] cs, int l, int r) {
        charc = cs[l]; cs[l] = cs[r]; cs[r] = c; }}Copy the code
class Solution {
    static char[] vowels = new char[] {'a'.'e'.'i'.'o'.'u'};
    static Set<Character> set = new HashSet<>();
    static {
        for (charc : vowels) { set.add(c); set.add(Character.toUpperCase(c)); }}public String reverseVowels(String s) {
        char[] cs = s.toCharArray();
        int n = s.length();
        int l = 0, r = n - 1;
        while (l < r) {
            if (set.contains(cs[l]) && set.contains(cs[r])) {
                swap(cs, l++, r--);
            } else {
                if(! set.contains(cs[l])) l++;if (!set.contains(cs[r])) r--;
            }
        }
        return String.valueOf(cs);
    }
    void swap(char[] cs, int l, int r) {
        charc = cs[l]; cs[l] = cs[r]; cs[r] = c; }}Copy the code
  • Time complexity: O(n)O(n)O(n)
  • Space complexity: due totoCharArrayWill create a new array, complexity is zero
    O ( n ) O(n)

The last

This is the no.345 of our “Brush through LeetCode” series. The series started on 2021/01/01, and there are 1916 questions on LeetCode by the start date. Some of them have locks, so we will finish all the questions without locks.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour… .

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.