[Easy] LeetCode - no.125 Valid Palindrome : Java

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

 

 

문제

주어진 String 값의 영어, 숫자만을 추려 소문자로 변환하였을 때 앞으로 읽거나 뒤로 읽거나 같은 경우(palindrome)일 경우 true 반환, 아니면 false 반환

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

 

 

 

풀이

class Solution {
    public boolean isPalindrome(String s) {
        StringBuilder sb = new StringBuilder();

        for (char c : s.toCharArray()) {
            if (Character.isAlphabetic(c) || Character.isDigit(c)) {
                sb.append(c);
            }
        }

        String s1 = sb.toString().toLowerCase();

        StringBuilder reverse = new StringBuilder();
        for (int i = sb.toString().length() - 1; i >= 0; i--) {
            reverse.append(sb.charAt(i));
        }

        String s2 = reverse.toString().toLowerCase();

        if (s1.equals(s2)) {
            return true;
        } else {
            return false;
        }
    }
}

• StringBuilder 사용
• Character.isAlphabetic()과 Character.isDigit()을 사용하여 조건에 맞는 문자만 sb에 저장
• sb.toString().toLowerCase()를 s1에 저장
• sb를 뒤에서부터 반대로 reverse라는 StringBuilder에 저장
• reverse.toString().toLowerCase()를 s2에 저장
• s1과 s2의 일치 여부를 반환
• 시간복잡도 : O(N)

 

더 좋은 방법에 대한 고민

• reverse를 따로 저장하는 것이 아닌, 앞 뒤로 포인터를 사용해서 하나의 문자열만으로 비교하는 방법

  public static boolean isPalindrome2(String s) {
  StringBuilder sb = new StringBuilder();

  for (char c : s.toCharArray()) {
    if (Character.isAlphabetic(c) || Character.isDigit(c)) {
      sb.append(Character.toLowerCase(c));
    }
  }

  int left = 0;
  int right = sb.toString().length() - 1;

  while (left < right) {
    if (sb.charAt(left) != sb.charAt(right)) {
      return false;
    }
    
    left++;
    right--;
  }
  
  return true;
}