[LeetCode] 125. Valid Palindrome

Problem

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.

Constraints:

• 1 <= s.length <= 2 * 10^5
• s consists only of printable ASCII characters.

Solution

Logic

1. 문자열 내의 문자를 하나하나 참조하여 영어 소문자와 숫자만 포함하는 새 문자열을 생성한다.

2. 새로 생성한 문자열이 palindrome인지 확인한다.

   Code

   class Solution {
    public boolean isPalindrome(String s) {
        String newS = "";
        for (int i = 0; i < s.length(); i++) { // n번
            if (48 <= s.charAt(i) && s.charAt(i) <= 57 || 97 <= s.charAt(i) && s.charAt(i) <= 122)
                newS += s.charAt(i);
            else if (65 <= s.charAt(i) && s.charAt(i) <= 90)
                newS += Character.toLowerCase(s.charAt(i));
        } for (int i = 0; i < newS.length() / 2; i++) // 1 ~ (n / 2)번
            if (newS.charAt(i) != newS.charAt(newS.length() - 1 - i))
                return false;
        return true;
    }
   }
   

   Time Complexity

   • 문자열 s의 길이를 n이라 가정할 때, 코드의 수행 시간을 좌우하는 것은 첫 번째 for반복문의 n번 계산 횟수이다. 따라서 본 솔루션은 O(n)의 시간 복잡도를 가진다.