LeetCode #125 Valid Palindrome 有效的回文

Klook.com
文章觀看次數: 383

英文原文如下

A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.

Given a string s, return true if it is a palindrome, or false otherwise.

中文翻譯

如果一個短語經過將大寫字母轉換為小寫並移除所有非字母跟數字的字元後，要是從前到後跟從後到前讀起來一樣，那他就是回文。

給予一個字串 s ，要是他是回文就回傳 true ，反之則為 false

範例及題目限制

解題思路

在這個問題，我們應該先把問題拆分成兩塊

  • 移除非字母數字的字元
  • 判斷剩下的文字是否為回文

➡ 可以參考之前跟回文有關的文章 – LeetCode #9 Palindrome Number 回文數字

至於如何移除非字母與數字的字元，我們可以使用ascii code的方式來輕鬆達成

C# 解決方案

方案1

public class Solution {
    public bool IsPalindrome(string s) {
        //1.remove non-alphanumeric characters
        List<char>list = new List<char>();
        
        s = s.ToLower();

        for (int i = 0; i < s.Length; i++)
        {
            char c = s[i];
            if ((c >= 'a' && c <= 'z') || (c >= '0' && c <= '9'))
            {
                list.Add(c);
            }
        }

        //2.check if Palindrome or not
        for(int i=0;i<list.Count/2;i++)
        {
            if(list[i] != list[list.Count-1-i]) 
            {
                return false;           
            }
        }
        return true;                   
    }
}

方案2

除了使用ascii code之外，其實不少語言都有內建的確認數字或字母的方法可以呼叫

public class Solution {
    public bool IsPalindrome(string s) {
        //1.remove non-alphanumeric characters
        List<char>list = new List<char>();
        
        s = s.ToLower();

        for (int i = 0; i < s.Length; i++)
        {
            char c = s[i];
            if (char.IsLetterOrDigit(c))
            {
                list.Add(c);
            }
        }

        //2.check if Palindrome or not
        for(int i=0;i<list.Count/2;i++)
        {
            if(list[i] != list[list.Count-1-i]) 
            {
                return false;           
            }
        }
        return true;                   
    }
}

Java解決方案

方案1

class Solution {
    public boolean isPalindrome(String s) {
        //1.remove non-alphanumeric characters
        List<Character> list = new ArrayList<>();

        s = s.toLowerCase();

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if ((c >= 'a' && c <= 'z') || (c >= '0' && c <= '9')) {
                list.add(c);
            }
        }

        //2.check if Palindrome or not
        for (int i = 0; i < list.size() / 2; i++) {
            if (list.get(i) != list.get(list.size() - 1 - i)) {
                return false;
            }
        }

        return true;
    }
}

方案2

class Solution {
    public boolean isPalindrome(String s) {
        //1.remove non-alphanumeric characters
        List<Character> list = new ArrayList<>();

        s = s.toLowerCase();

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (Character.isLetterOrDigit(c)) {
                list.add(c);
            }
        }

        //2.check if Palindrome or not
        for (int i = 0; i < list.size() / 2; i++) {
            if (list.get(i) != list.get(list.size() - 1 - i)) {
                return false;
            }
        }

        return true;
    }
}

Python3 解決方案

方案1

class Solution:
    def isPalindrome(self, s: str) -> bool:
        list = []

        s = s.lower()

        for c in s:
            if (c >= 'a' and c <= 'z') or (c >= '0' and c <= '9'):
                list.append(c)

        for i in range(len(list) // 2):
            if list[i] != list[-1 - i]:
                return False

        return True

方案2

class Solution:
    def isPalindrome(self, s: str) -> bool:
        list = []

        s = s.lower()

        for c in s:
            if c.isalnum():
                list.append(c)

        for i in range(len(list) // 2):
            if list[i] != list[-1 - i]:
                return False

        return True

JavaScript 解決方案

方案1

/**
 * @param {string} s
 * @return {boolean}
 */
var isPalindrome = function(s) {
    let arr = [];
    
    s = s.toLowerCase();
    
    for (let i = 0; i < s.length; i++) {
        let c = s.charAt(i);
        if ((c >= 'a' && c <= 'z') || (c >= '0' && c <= '9')) {
            arr.push(c);
        }
    }
    
    for (let i = 0; i < arr.length / 2; i++) {
        if (arr[i] !== arr[arr.length - 1 - i]) {
            return false;
        }
    }
    
    return true;
};

因 JS 沒有內建判斷的方法可以呼叫，故先讓我想想還有甚麼可以取代的…

結論

這一題其實根本就是當初第9題的進階版哈哈

要是有寫過的話，那對於判斷應該是相當輕鬆的!

🧡如果這篇文章有幫上你的一點點忙，那是我的榮幸

🧡收藏文章或幫我分享，我都會很感謝的

✅如有任何疑問，歡迎透過留言或messenger讓我知道 !

題目連結 : Valid Palindrome – LeetCode

一些隨機文章

相關文章

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *