#125 Valid Palindrome

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

문제 조건

• 1 <= s.length <= 2 * 10^5
• string s는 능한 ASCII 문자로만 구성됩니다.
  string s가 주어졌을 때 회문이면 true를 아니면 false를 반환합니다.

문제 해결

문제 해결 로직

해당 문제는 문자열의 앞과 뒤에서 글자들을 비교하여 풀 수 있다.
앞과 뒤에서 빠르게 문자를 가져오기위해 투 포인터를 사용하여 반복문을 통해 쉽게 구할 수 있다.

데이터 입력

문제에서 입력이 들어오는 데이터는 String s 하나지만 위치 관리를 위해 필요한 변수를 미리 선언해야합니다.

• startIndex
  앞에서 부터 세는 index
• endIndex
  뒤에서 부터 세는 index
• processedString
  띄워쓰기 제거, 특수문자 제거, 소문자로 변경 작업을 거친 문자열

        String processedString = s.replaceAll("[^a-zA-Z0-9]", "").toLowerCase();
        // 정규 표현식을 사용하여 a~z, A~Z, 0~9까지만 데이터를 남겨둠.
        
        int startIndex = 0;
        int endIndex = processedString.length() - 1;  // Index는 길이 - 1

회문 확인

비교를 시작할 위치를 정했고, 이제 반복문을 통해 해당 위치의 값을 비교한다.
단, 서로의 위치가 교차되지 않도록 조건을 걸어준다.

for(;startIndex<endIndex;startIndex++,endIndex--){
	if(processedString.charAt(startIndex) != processedString.charAt(endIndex)){
		return false;
    }
}

return true;

코드 작성

class Solution {
    public boolean isPalindrome(String s) {
        String processedString = s.replaceAll("[^a-zA-Z0-9]", "").toLowerCase();
        
        int startIndex = 0;
        int endIndex = processedString.length() - 1;

        for(;startIndex<endIndex;startIndex++,endIndex--){
          if(processedString.charAt(startIndex) != processedString.charAt(endIndex)){
            return false;
          }
        }

        return true;
    }
}

복잡도 계산

• 시간 복잡도

  • 문자열을 정규식 처리 후 processedString 변수에 저장한다. 이것의 시간 복잡도는 입력 문자열의 길이인 O(n)
  • 반복문은 문자열 중간까지 순회하며 해당 위치의 문자열을 비교한다. 이것의 시간 복잡도는 O(n/2)이다.
  • 따라서 총 시간 복잡도는 O(n) + O(n/2) = O(n)이 된다.

• 공간 복잡도

  • processedString 변수가 변환한 string 만큼의 데이터를 저장하기 때문에 O(n)의 공간 복잡도를 가진다.
  • 이 외의 변수는 상수형 데이터만 가지고 있기 떄문에 O(1)의 공간 복잡도를 가진다.
  • 따라서 총 공간 복잡도는 O(n) + O(1) = O(n)이 된다.

회고

• 다음과 같은 점수를 기록했다.
  

• 공간 복잡도가 O(1)을 가지기 위해서는 변환 후 저장하지 않고 해당 과정을 수행하면 된다.

  • char로 해당 위치의 데이터를 가져온다.
  • Character.isLetterOrDigit(해당 char)을 사용하여 해당 값이 필요없다면 Index를 이동한다
  • 해당 과정을 거쳐 문자 혹은 숫자를 비교한다. 이때 Character.toLowerCase(해당 char)을 사용하여 소문자화를 진행한다.