알고리즘/String
Leet code (Easy): 125. Valid Palindrome (투 포인터) - Java
mezo
2024. 10. 28. 11:31
728x90
반응형
20. Valid Parentheses 문제를 풀때는 괄호가 선입후출로 다 닫히는지 보는문제였기 때문에 Stack을 사용했다.
그러나 이문제는 Palindrome 문제로
문자, 기호, 숫자 등이 포함된 문자열에서 문자와 숫자가 대칭을 이루는지 확인하는 문제이다.
따라서 Stack을 사용하기보다 투 포인터로 가장자리부터 문자와 숫자를 만나면 두 포인터가 가리키는 문자/숫자가 일치하는지 확인하는 방식으로 진행하는 것이 공간복잡도는 O(1)이고, 시간복잡도는 O(N) 으로 효율적이다.
class Solution {
public boolean isPalindrome(String s) {
if(s.isEmpty()){
return true;
}
int left = 0;
int right = s.length() - 1;
while(left <= right){
char currLeft = s.charAt(left);
char currRight = s.charAt(right);
if(!Character.isLetterOrDigit(currLeft)){
left++;
} else if(!Character.isLetterOrDigit(currRight)){
right--;
} else{
if(Character.toLowerCase(currLeft) != Character.toLowerCase(currRight)){
return false;
}
left++;
right--;
}
}
return true;
}
}
728x90
반응형