iT邦幫忙

DAY 21
1

連續30天,挑戰演算法系列 第 21

[Day21] 30 天挑戰演算法 - 迴文

題目來源Valid Palindrome

問題
給予一個字串,確認它是否為迴文,無論字串內容為何,都只考慮字母和數字,並且忽略大小寫。
例如:
"A man, a plan, a canal: Panama" 是迴文
"race a car" 不是迴文

另外,在這個題目中,我們定義 空字串 是迴文

想法:
昨天我們在驗證 數字迴文 時,我們是用 左右比較的方式來驗證迴文。而這次文字比較雖然也是可以用相同的法!不過,今天想用另一種方式來解這題,並且今天也多了一點東西要處理。首先,我們先來看題目有哪些限制:

  1. 迴文判斷只考慮 字母數字
  2. 迴文判斷 忽略大小寫

既然迴文的定義就是從左念過來,或從右唸過來都要相等,那麼這題我們就可以使用另一個方式來判斷是否為迴文。那就是將文字反轉,再判斷輸入的文字和反轉過後的文字是否相等,若相等,他就是迴文了。

所以我們的判斷步驟如下:

  1. 將文字全部轉成小寫
  2. 過濾掉不需要比較的文字
  3. 反轉輸入字串到新字串
  4. 比較新字串與輸入字串是否相等

有了判斷步驟,就可以依照判斷的步驟直接將程式碼給寫下來了!

public bool isPalindrome(string input_string) {
   // 既然題目說忽略大小寫,在這邊我就全部用小寫來處理
    input_string = input_string.ToLower();

    StringBuilder builder = new StringBuilder();
    for (int i = 0; i < input_string.Length; i++) {
        // 在這邊只處理 數字和文字
        if (isAlphanumeric(input_string[i]))
            builder = builder.Append(input_string[i]);        
    }

    return builder.ToString() == Reverse(builder.ToString());
    
}

// 將數字反轉
public string Reverse(string input) {
    char[] charArray = input.ToArray();
    Array.Reverse(charArray);
    return new string(charArray);
}

// 是否為文字或數字
public bool isAlphanumeric(char c) {
    if (c >= '0' && c <= '9')
        return true;
    else if (c >= 'a' && c <= 'z')
        return true;

    return false;
}

不過,這題如果改用 Python 來做的話,會更酷!解答如下:

判斷迴文 (Python 版本)
def is_palindrome(input):
    palindromeString = [i.lower() for i in input if input.isalnum()]
    return palindromeString == palindromeString[::-1]

酷吧!


上一篇
[Day20] 30 天挑戰演算法 - 迴文數字
下一篇
[Day22] 30 天挑戰演算法 - 合併兩個已排序的陣列
系列文
連續30天,挑戰演算法30

尚未有邦友留言

立即登入留言