[LeetCode] 125. Valid Palindrome

https://leetcode.com/problems/valid-palindrome/description/?envType=study-plan-v2&envId=top-interview-150 

Valid Palindrome - LeetCode

문제 유형 : 문자열 처리 / 투 포인터

문제 난이도 : Easy

 

문제

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가 회문인지(뒤집어도 같은 문자열인지)확인하는 코드를 작성하시오. 대소문자 구분은 없고, 특수문자 및 공백은 무시합니다.

 

풀이

문자열의 양 끝부터 시작해서 비교해주면된다.

특수문자 및 공백을 없애는 함수를 만들어서 퓨어한 alphanumeric 문자열을 만들어도 되고,

탐색 중에 건너뛰는 옵션도 있다.

 

코드

C++ - alphanumeric 문자열을 만든 풀이

class Solution {
public:
    string toAlphanumeric(string str) {
        for (int i = 0; i < str.size(); i++) {
            if (str[i] >= 65 && str[i] <= 90 || str[i] >= 97 && str[i] <= 122 || str[i] >= 48 && str[i] <= 57) {
                str[i] = tolower(str[i]);
                continue;
            } else {
                str[i] = ' ';
            }
        }
        str.erase(remove(str.begin(), str.end(), ' '), str.end());
        return str;
    }
    
    bool isPalindrome(string s) {
        s = toAlphanumeric(s);
        int left = 0, right = s.size() - 1;

        while (left <= right) {
            if (s[left] != s[right]) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
};

 

C++ - isalnum 함수를 이용한 풀이

class Solution {
public:
    bool isPalindrome(string s) {
        
        int left = 0, right = s.size() - 1;

        while (left <= right) {
            if(!isalnum(s[left])) left++;
            else if(!isalnum(s[right])) right--;
            else if (tolower(s[left]) != tolower(s[right])) {
                return false;
            }
            else{
                left++;
                right--;
            }
        }
        return true;
    }
};

 

Python3

class Solution:
    def isPalindrome(self, s: str) -> bool:
        left, right = 0, len(s) - 1

        while left <= right:
            if not s[left].isalnum():
                left += 1
            elif not s[right].isalnum():
                right -= 1
            elif s[left].lower() != s[right].lower():
                return False
            else:
                left += 1
                right -= 1
        return True

 

Dart(...)

class Solution {
  bool isAlphanumeric(String c){
      if(RegExp(r'^[a-zA-Z0-9]+$').hasMatch(c)){
        return true;
      } else {
        return false;
      }
  }

  bool isPalindrome(String s) {
    int left = 0;
    int right = s.length - 1;

    while (left <= right) {
      if (!isAlphanumeric(s[left])) {
        left++;
      } else if (!isAlphanumeric(s[right])) {
        right--;
      } else if (s[left].toLowerCase() != s[right].toLowerCase()) {
        return false;
      } else {
        left++;
        right--;
      }
    }
    return true;
  }
}

 

Java

class Solution {
    public boolean isPalindrome(String s) {
        int left = 0, right = s.length()-1;

        while(left <= right){
            if(!Character.isLetterOrDigit(s.charAt(left))) left++;
            else if(!Character.isLetterOrDigit(s.charAt(right))) right--;
            else if(Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {
                return false;
            } else {
                left++;
                right--;
            }
        }
        return true;
    }
}

 

Swift

class Solution {
    func isPalindrome(_ s: String) -> Bool {
        var left = s.startIndex, right = s.index(before: s.endIndex)

        while left < right {
            if !s[left].isLetter && !s[left].isNumber {
                left = s.index(after: left)
            } else if !s[right].isLetter && !s[right].isNumber {
                right = s.index(before: right)
            } else if s[left].lowercased() != s[right].lowercased() {
                return false
            } else {
                left = s.index(after: left)
                right = s.index(before: right)
            }
        }
        return true
    }
}