345. Reverse Vowels of a String (使用 C 語言解題)

345. Reverse Vowels of a String

Solved

Easy

Topics

Companies

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

The vowels are 'a', 'e', 'i', 'o', and 'u', and they can appear in both lower and upper cases, more than once.

 

Example 1:

Input: s = "hello"
Output: "holle"

Example 2:

Input: s = "leetcode"
Output: "leotcede"

 

Constraints:

• 1 <= s.length <= 3 * 105
• s consist of printable ASCII characters.

 google 翻譯：

給定一個字串 s，僅反轉字串中的所有元音並傳回它。

元音為“a”、“e”、“i”、“o”和“u”，它們可以以小寫和大寫形式出現多次。

想法一：

給定兩個指標，一個從頭開始++，一個從結尾開始--。
先從頭找最近的元音，再從結尾找最近的元音，
要是 頭<尾，則表示未過半，就兩個互換。

寫法一：

// 判斷是否是元音
bool isVowels(char c) {
    if(c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u')
        return true;
    else if(c == 'A' || c == 'E' || c == 'I' || c == 'O' || c == 'U')
        return true;
    return false;
}

char* reverseVowels(char* s) {
    char *p1, *p2, c;
    int find1, find2;
    p1 = s; // 設定從頭++指標
    p2 = s + strlen(s)-1; // 設定從結尾--指標
    while(p1< p2) { // 判斷兩個指標沒有超過彼此
        // 從頭++找元音
        find1 = 0;
        for(; *p1; p1++) {
            if(isVowels(*p1)) {
                find1 = 1;
                break;
            }
        }
        
        // 從結尾--找元音
        find2 = 0;
        for(; p2 >= s; p2--) {
            if(isVowels(*p2)) {
                find2 = 1;
                break;
            }
        }
        
        // 都有找到元音，並且兩個指標沒有超過彼此，則互換
        if(find1 && find2 && p1<p2) {
            c = *p1;
            *p1 = *p2;
            *p2 = c;
            p1++; // 指標指到下一個
            p2--; // 指標指到下一個
        }
    }

    return s;
}

結果一：

結果差強人意，速度普普...

想法二：

從 for 改用 while 看看速度是否有差異...

寫法二：

// 判斷是否是元音
bool isVowels(char c) {
    if(c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u')
        return true;
    else if(c == 'A' || c == 'E' || c == 'I' || c == 'O' || c == 'U')
        return true;
    return false;
}

char* reverseVowels(char* s) {
    char *p1, *p2, c;
    int find1, find2;
    p1 = s; // 設定從頭++指標
    p2 = s + strlen(s)-1; // 設定從結尾--指標
    while(p1< p2) { // 判斷兩個指標沒有超過彼此
        // 從頭++找元音
        find1 = 0;
        while(*p1) { // 從 for 改用 while
            if(isVowels(*p1)) {
                find1 = 1;
                break;
            }
            p1++;
        }

        // 從結尾--找元音
        find2 = 0;
        while(p2 >= s) { // 從 for 改用 while
            if(isVowels(*p2)) {
                find2 = 1;
                break;
            }
            p2--;
        }

        // 都有找到元音，並且兩個指標沒有超過彼此，則互換
        if(find1 && find2 && p1<p2) {
            c = *p1;
            *p1 = *p2;
            *p2 = c;
            p1++; // 指標指到下一個
            p2--; // 指標指到下一個
        }
    }

    return s;
}

結果二：

所以是 while 速度比 for 快嗎？還是只是剛好而已...

想法三：

研究了大神的寫法，果然簡潔多了。馬上來試看看效能如何...

寫法三：

// 判斷是否是元音
bool isVowels(char c) {
    c = tolower(c);
    if(c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u')
        return true;
    return false;
}

char* reverseVowels(char* s) {
    char *p1, *p2, c;
    p1 = s; // 設定從頭++指標
    p2 = s + strlen(s)-1; // 設定從結尾--指標
    while(p1< p2) { // 判斷兩個指標沒有超過彼此
        if(isVowels(*p1)) { // 開頭是元音才進來
            while(p2 >= s && !isVowels(*p2)) // 找結尾的元音
                p2--;

            // 都有找到元音，並且兩個指標沒有超過彼此，則互換
            if(p1 < p2) {
                c = *p1;
                *p1 = *p2;
                *p2 = c;
                p2--;
            } else
                break;
        }
        p1++;
    }

    return s;
}

結果三：

雖然效能差不多，但簡潔也是有好處的