[LeetCode 125] Valid Palindrome - 유효한 회문 판단하기

🔗 문제 링크: https://leetcode.com/problems/valid-palindrome/

---

📌 문제 설명

주어진 문자열 s가 알파벳과 숫자만 고려하고, 대소문자 구분 없이 앞뒤가 같은 회문(palindrome)인지 판별하는 문제입니다.

🔹 조건 요약

• 영문자와 숫자만 유효 문자로 간주
• 대소문자 구분 없이 비교
• 회문: 앞에서 읽어도, 뒤에서 읽어도 같은 문자열

---

✅ 해결 아이디어 - Two Pointers

이 문제는 양쪽 끝에서 문자를 비교하며 회문 여부를 판단하는 투 포인터(Two Pointers) 알고리즘으로 풀 수 있습니다.

🔹 전략

• left, right 두 포인터를 사용해 문자열의 양쪽 끝에서 시작
• 알파벳/숫자가 아닌 문자는 건너뜀
• 영문자는 소문자로 통일 후 비교
• 두 문자가 다르면 false 반환, 끝까지 같으면 true

---

✅ 구현 코드 (TypeScript)

export function isPalindrome(s: string): boolean {
  let left = 0;
  let right = s.length - 1;

  const makeLower = (char: string) => {
    if (char >= "A" && char <= "Z") {
      return String.fromCharCode(char.charCodeAt(0) + 32);
    } else if (char >= "a" && char <= "z") {
      return char;
    } else if (char >= "0" && char <= "9") {
      return char;
    } else {
      return "";
    }
  };

  while (left < right) {
    const l = makeLower(s[left]);
    const r = makeLower(s[right]);

    if (l === "") {
      left++;
      continue;
    }
    if (r === "") {
      right--;
      continue;
    }
    if (l !== r) {
      return false;
    }

    left++;
    right--;
  }

  return true;
}

---

🧪 테스트 코드 (Jest)

describe("LeetCode 125: Valid Palindrome", () => {
  it("simple palindrome", () => {
    expect(isPalindrome("A man, a plan, a canal: Panama")).toBe(true);
  });

  it("not a palindrome", () => {
    expect(isPalindrome("race a car")).toBe(false);
  });

  it("empty string", () => {
    expect(isPalindrome("")).toBe(true);
  });

  it("numbers and letters", () => {
    expect(isPalindrome("0P")).toBe(false);
  });
});

---

✅ 시간 및 공간 복잡도

항목 복잡도

시간	O(N) - 문자열 한 번 순회
공간	O(1) - 추가 메모리 거의 없음 (포인터만 사용)

---

✅ 마무리 정리

• 핵심은 알파벳과 숫자만 추려서 비교하는 것
• 앞뒤 포인터를 사용하면 한 번의 순회로 문제 해결 가능
• 문자열 전처리 없이도 바로 비교하며 진행하는 방식이 효율적