[LeetCode] - E - Valid Palindrome

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

Valid Palindrome - LeetCode

 

📌 - 처음 생각한 풀이

1. 대문자 알파벳일 경우 소문자로 변경하고 sb에 더해주고
2. 소문자일 경우 그대로 append
3. 숫자일 경우 그대로 append
4. 이 외의 경우에는 제거 하는 방식으로 sb를 만들어주고 해당하는 문자를 처음부터 size/2만큼 앞뒤 비교하면서 다르면 false;

예상은 했지만, 시간과 메모리 전부 최악..

🔥 - Java 코드

import java.util.*;
class Solution {
    public boolean isPalindrome(String s) {

        StringBuilder sb = new StringBuilder();
        for(int i =0;i<s.length();i++){
            int number = s.charAt(i) - 0;
            System.out.println(number);
            if(number >= 65 && number <=90){
                number += 32;
                sb.append((char)number);
            }else if(number >=97 && number <= 122){
                sb.append((char)number);
            }else if(number >=48 && number <= 57 ){
                sb.append((char)number);
            }

        }


        System.out.println(sb);
        for(int i =0;i<sb.length()/2;i++){
            if(sb.charAt(i) != sb.charAt(sb.length()-i-1)){
                return false;
            }
        }

        return true;
    }
}

 

📌- 개선된 방식

1. 위의 방식과 같이 아스키 코드로 대문자 소문자 나눔
2. 오른쪽, 왼쪽을 투포인터로 관리하면서 하나씩 증가 및 감소 시키면서 비교
3. 다를 경우 return false;

-> 이 방식으로 하게 되면 위의 경우처럼 하나의 문자열로 다시 만들어 줄 필요가 없어서 속도, 메모리에서 굉장히 효율적이다.

🔥 - Java 코드

 

import java.util.*;
class Solution {
    public boolean isPalindrome(String s) {
      if (s == null || s.isEmpty()) {  
            return true;  
        }  
        int left = 0;  
        int right = s.length() - 1;  
        while (left < right) {  
            while (left < right &&  
                   !((s.charAt(left) >= 65 && s.charAt(left) <= 90) ||  
                     (s.charAt(left) >= 97 && s.charAt(left) <= 122) ||  
                     (s.charAt(left) >= 48 && s.charAt(left) <= 57))) {  
                left++;  
            }  
            while (left < right &&  
                   !((s.charAt(right) >= 65 && s.charAt(right) <= 90) ||  
                     (s.charAt(right) >= 97 && s.charAt(right) <= 122) ||  
                     (s.charAt(right) >= 48 && s.charAt(right) <= 57))) {  
                right--;  
            }  
            if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {  
                return false;  
            }  
            left++;  
            right--;  
        }  
        return true;  
    }
}