[Dart] 125. Valid Palindrome

1. 문제

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

 

 

 

2. 요구사항

1) 팰린드롬은 모든 대문자를 소문자로 바꾸고, 모든 영숫자가 아닌 문자를 제거한 후, 앞뒤로 읽어도 같은 구문이다.

2) 문자열 s가 주어진 후, 팰린드롬이면 true를 반환하고, 아니면 false를 반환한다.

 

 

3. 핵심 아이디어

1) 문자열 전처리 후, 문자 비교

 

주어지는 문자열에는 공백과 특수 문자가 있으며, 대문자와 소문자가 나누어져 있다.

이를 순수한 소문자 문자열로 바꾸기 위해 전처리 과정을 거친다.

String result = s.replaceAll(RegExp('[^a-zA-Z0-9]'), "").toLowerCase();

 

정규표현식을 사용해 영문자(a-z, A-Z)와 숫자(0-9)를 제외한 모든 문자를 제거한다.

이후, toLowerCase()로 대문자를 소문자로 변경한다.

 

여기서 정규표현식(Regular Expression, RegExp)은 문자열에서 특정한 패턴을 찾거나 바꾸기 위한 이다.

구성 요소	의미
[ ]	문자 집합: 안에 있는 문자 중 하나를 의미
a-z	소문자 알파벳 a부터 z까지
A-Z	대문자 알파벳 A부터 Z까지
0-9	숫자 0부터 9까지
^	부정(negation): 이 집합 외의 문자를 의미

 

 

2) 팰린드롬 판별

int first = 0;
int end = result.length - 1;

while(first < end) {
  if(result[first] == result[end]) {
    first++;
    end--;
  } else {
    return false;
  }
}

 

first는 문자열의 앞쪽 인덱스, end는 뒤쪽 인덱스를 가리킨다.

두 포인터를 양쪽에서 좁혀가며 문자를 비교하여 두 문자가 같으면 다음 문자를 비교하고,

두 문자가 다르면 바로 false를 반환한다.

 

 

3) 코드

class Solution {
  bool isPalindrome(String s) {
  
    // 공백, 특수문자 제거 후, 소문자로 변경
    String result = s.replaceAll(RegExp('[^a-zA-Z0-9]'), "").toLowerCase();

    int first = 0;
    int end = result.length - 1;

    // while 문을 이용한 문자열 비교
    while(first < end) {
      if(result[first] == result[end]) {
        first++;
        end--;
      } else {
        return false;
      }
    }
    return true;
  }
}