Leetcode 125 Valid Palindrome

Soru

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.

Örnek 1

Input: s = "A man, a plan, a canal: Panama"
Output: true
Explanation: "amanaplanacanalpanama" is a palindrome.

Örnek 2

Input: s = "race a car"
Output: false
Explanation: "raceacar" is not a palindrome.

Örnek 3

Input: s = " "
Output: true
Explanation: s is an empty string "" after removing non-alphanumeric characters.
Since an empty string reads the same forward and backward, it is a palindrome.

Çözüm

• eetCode’un “125. Valid Palindrome” sorusu, verilen bir stringin, yalnızca alfanümerik karakterleri dikkate alarak ve büyük/küçük harf duyarlılığını göz ardı ederek bir palindrom(düze ve ters okunuşu aynı) olup olmadığını kontrol etmenizi ister.
• Bu sorun için en etkili yöntemlerden biri, iki işaretçi kullanmaktır. Bir işaretçi stringin başında, diğer işaretçi ise sonunda başlar. İki işaretçi birbirine doğru hareket ederken, sadece alfanümerik karakterleri kontrol eder ve karşılaştırır.
• İşaretçilerin İnitialize Edilmesi: left işaretçisi stringin başında, right işaretçisi ise sonunda başlar.
• Alfanümerik Olmayanların Atlaması: Her iki işaretçi için, gösterdikleri karakter alfanümerik değilse, bir sonraki alfanümerik karaktere kadar hareket ederler.
• Karakter Karşılaştırması: İşaretçiler alfanümerik bir karaktere işaret ettiğinde, bu karakterler karşılaştırılır. Eğer bir uyuşmazlık varsa, string bir palindrom değildir.
• İşaretçilerin Güncellenmesi: Karakterler eşleşiyorsa, left bir arttırılır, right bir azaltılır ve döngü devam eder.
• Sonuç: Tüm karşılaştırmalar geçerli ise ve hiçbir çelişki bulunmazsa, string bir palindromdur.

Code

    def isPalindrome(self, s: str) -> bool:
        l, r = 0, len(s) - 1
        
        while l<r:
            # Sol işaretçi için alfanümerik olmayanları atla
            while l < r and not self.alphaNum(s[l]):
                l +=1
            # Sağ işaretçi için alfanümerik olmayanları atla    
            while r > l and not self.alphaNum(s[r]):
                r-=1
            # Karşılaştırma yap, büyük/küçük harf duyarlılığını göz ardı et    
            if s[l].lower() != s[r].lower():
                return False
            l,r = l +1,r-1
        return True
    
    def alphaNum(self,c):
        return(ord('A')<=ord(c) <= ord('Z') or
               ord('a')<=ord(c) <= ord('z') or
               ord('0')<=ord(c) <= ord('9'))

Complexity

• Time complexity(Zaman Karmaşıklığı): O(n), burada n stringin uzunluğudur. String yalnızca bir kez taranır.
• Space complexity(Alan Karmaşıklığı): O(1), çünkü ekstra bir alan kullanılmaz ve sadece birkaç yerel değişken tanımlanır.