[Algorithm] Valid Palindrome

Palindrome : 회문(回文) 또는 팰린드롬(palindrome)은 거꾸로 읽어도 제대로 읽는 것과 같은 문장이나 낱말, 숫자, 문자열(sequence of characters) 등입니다.

 

Question :

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.

Example 1:

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

 

Example 2:

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

 

Example 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.

 

주어진 문제는 회문 또는 팰린드롬에 관한 문제로 앞으로 읽어도 뒤에서 부터 읽어도 같은 문장이 되는 것을 찾는 것입니다. 거기에 조건이 대문자를 모두 소문자로 변경하고 알파벳이외의 문자는 삭제하는 조건이 붙었습니다. 알파벳문자와 숫자만이 가능합니다. 앞에서부터 읽어도 뒤어서 부터 읽어도 같은 문장이나 단어이면 참(true), 같지 않으면 거짓(false)를 결과값으로 리턴을 합니다.

 

Solution :

 

주어진 문제를 풀기 위해서 우선 소문자로 변경하기위해 ToLower()함수를 사용하고, 문자와 숫자만을 사용해야 하므로 IsLetterOrDigit()함수를 사용하여 조건을 만족시킵니다.

While반복문을 이용하여 왼쪽부터 읽은 문자나 숫자와 오른쪽부터 읽은 문자나 숫자를 비교하여 왼쪽에서 시작한 인덱스가 오른쪽에서 시작한 인덱스가 같거나 작아질때까지 반복해 줍니다.

 

public class Solution {
    public bool IsPalindrome(string s) {
        string str = s.ToLower(); // 소문자로 변경
        int l=0, r = str.Length-1;

        while(l<=r){
            //if any charater is other than letter or digit while moving from left
            if(!char.IsLetterOrDigit(str[l])){ // 왼쪽에서 시작하는 캐릭터가 문자나 숫자가 아닐 경우 다음 캐릭터로 이동 하기 위해 인덱스 추가
                l++;
            }
             //if any charater is other than letter or digit while moving from right
            else if (!char.IsLetterOrDigit(str[r])){ // 오른쪽에서 시작하는 캐릭터가 문자나 숫자 아닐 경우 다음 캐릭터로 이동 하기 위해 인덱스를 감소
                r--;
            }
             //if from both sides it is correct
            else{
                if(str[l]!= str[r]){ // 두 문자나 숫자를 비교, 같지 않을 경우 거짓을 리턴
                    return false;
                }
                l++; // 다음 캐릭터로 이동 하기 위해 왼쪽 인덱스 증가  
                r--; // 다음 캐릭터로 이동 하기 위해 오른쪽 인덱스 감소
            }
        }

    return true; // 반복문이 끝난 후에 모든 비교가 참일경우 참을 리턴
    }
}

Initialize two pointers, "left" at the beginning of the string and "right" at the end of the string.
Iterate through the string using a while loop until "left" is less than or equal to "right".
Within the loop:

a. Convert into lowercase letters
b. Check if the character at index "left" is lettter or number. If not, increment "start".
b. Check if the character at index "right" is lettter or number . If not, decrement "right".
c. If both characters are lettter or number , compare them.
d. If the characters are not equal, return false as the string is not a palindrome.
e. If the characters are equal, increment "left" and decrement "right" to continue the comparison.
If the loop completes without finding any unequal pairs of alphanumeric characters, return true, indicating that the string is a palindrome.

 

다른 방법:

using System.Text.RegularExpressions;

public class Solution {
    public bool IsPalindrome(string s) {
        string k = Regex.Replace(s.ToLower(), "[^a-zA-Z0-9]", "");
                        
        for(int i=0;i<k.Length/2;i++) // 해당 문자를 중간까지만 처리하도록 함   
        {
            if(k[i] != k[k.Length-1-i]) // compare charactor between first++ and last-- 순차적으로 문자를 비교
            {
                return false;           // if any char not the same, return false 값이 같지 않다면 거짓을 리턴
            }
        }
        return true;
    }
}