회문을 검증하는 방법

str 문자열이 주어지면 회문이면 True를 반환하고 그렇지 않으면 False를 반환하는 메서드를 작성할 수 있습니까? 기억하시겠지만 apalindrome는 "뒤에서 읽어도 앞으로 읽어도 같은 단어, 구 또는 시퀀스"로 정의됩니다. 지금은 특수 문자나 공백을 포함하는 입력 문자열이 없다고 가정하므로 다음 예가 적용됩니다.

let str = 'thisisnotapalindrome';
isPalindrome(str);
// false

str = 'racecar';
isPalindrome(str);
// true

추가 문제로 영숫자가 아닌 문자는 무시하십시오. 우리가 제시하는 최종 솔루션은 모든 엣지 케이스를 처리합니다.



이 강의는 원래 https://algodaily.com에 게시되었으며, 여기서 저는 기술 인터뷰 과정을 유지하고 야심 찬 개발자를 위한 아이디어를 작성합니다.

참 또는 거짓?

문자열의 반전이 원래 문자열과 같으면 문자열이 회문으로 정의됩니다.

예를 들어 "toot"는 회문이지만 "boot"는 회문이 아닙니다.

해결책: 사실


이것은 고전적인 질문이며 이를 해결하는 여러 가지 방법이 있습니다. 학습을 위해 모두 다루자!

기본 제공 메서드 사용

이는 실제 인터뷰에서는 유효하지 않을 수 있지만 기본 제공String 방법을 사용하여 빠른 반전을 수행할 수 있습니다. Javascript에서는 단순히 reverse()를 호출할 수 있고 Python에서는 [::-1]를 호출할 수 있습니다. 그런 다음 반전된 문자열을 원본과 비교할 수 있습니다.

function isPalindrome(str) {
    // Calling reverse function
    const reversed = str.split('').reverse().join('');

    // Checking if both strings are equal or not
    if (str == reversed) {
        return true;
    }
    return false;
}

console.log(isPalindrome('racecar'));

주문하다

문자열이 회문인지 성공적으로 알아내는 순서는 무엇입니까?

낮음이 높음보다 작은 동안 수행하기 위해 while 루프를 엽니다

.

루프가 끝날 때까지 계속하고 true를 반환합니다

.

high 및 low의 두 변수를 0 및 (문자열 길이 - 1)로 정의합니다.

`string[low]`가 `string[high]`와 같지 않으면 false를 반환합니다. 낮은 값 증가, 높은 값 감소

해결책:

루프가 끝날 때까지 계속하고 true를 반환합니다

.

`string[low]`가 `string[high]`와 같지 않으면 false를 반환합니다. 낮은 값 증가, 높은 값 감소

낮음이 높음보다 작은 동안 수행하기 위해 while 루프를 엽니다

.

high 및 low의 두 변수를 0 및 (문자열 길이 - 1)로 정의합니다.

다중 선택

다음 의사 코드는 입력 문자열에 무엇을 합니까?

def reverse_str(str):
  start = 0
  end = len(str)-1
  str_copy = [letter for letter in str]
  while start < end:
    temp = str_copy[start]
    str_copy[start] = str_copy[end]
    str_copy[end] = temp
    start += 1
    end -= 1
  return "".join(str_copy)

복사본 만들기

문자열 반전

첫 글자와 마지막 글자 바꾸기

무한 루프

솔루션: 문자열 반전

while 루프 사용:

len(str)-1 반복을 수행할 필요가 없다는 것을 인식하여 작업 수를 줄일 수 있습니다. 끝에서 문자열을 단순히 반복하는 하나의 포인터를 사용하는 대신 두 개를 사용하지 않는 이유는 무엇입니까?

function isPalindrome(str) {
    let left = 0;
    let right = str.length - 1;
    let leftChar;
    let rightChar;

    while (left < right) {
        leftChar = str.charAt(left);
        rightChar = str.charAt(right);

        if (leftChar == rightChar) {
            left++;
            right--;
        } else {
            return false;
        }
    }

    return true;
}

console.log(isPalindrome('racecar'));

위에서 우리가 하고 있는 것은 start 및 end 두 개의 포인터를 지정하는 것입니다. start는 문자열의 시작 부분을 가리키고 end는 마지막 문자를 가리키는 포인터입니다. 예제 입력racecar을 실행하면서 다음과 같은 비교 결과를 볼 수 있습니다.

racecar
^     ^
racecar
 ^   ^
racecar
  ^ ^
racecar
   ^
True

다중 선택

다음 코드의 실행 시간은 얼마입니까?

def reverse_str(str):
  start = 0
  end = len(str)-1
  str_copy = [letter for letter in str]
  while start < end:
    temp = str_copy[start]
    str_copy[start] = str_copy[end]
    str_copy[end] = temp
    start += 1
    end -= 1
  return "".join(str_copy)

O(log n)

O(n)

O(n log n)

O(n^2)

솔루션: O(n)

마지막 해결책

function isPalindrome(str) {
  if (!str || str === "") {
    return true;
  } else {
    let left = 0;
    let right = str.length - 1;
    let leftChar;
    let rightChar;

    while (left < right) {
      leftChar = str.charAt(left).toLowerCase();
      rightChar = str.charAt(right).toLowerCase();

      if (isAlphaNumeric(leftChar) && isAlphaNumeric(rightChar)) {
        if (leftChar == rightChar) {
          left++;
          right--;
        } else {
          return false;
        }
      } else {
        if (!isAlphaNumeric(leftChar)) {
          left++;
        }
        if (!isAlphaNumeric(rightChar)) {
          right--;
        }
      }
    }

    return true;
  }
}

function isAlphaNumeric(c) {
  if (/[^a-zA-Z0-9]/.test(c)) {
    return false;
  } else {
    return true;
  }
}

console.log(isPalindrome("A Santa Lived As a Devil At NASA"));

technical challenges at AlgoDaily.com에 대한 더 많은 시각적 자습서를 확인하고 our daily coding problem newsletter을 사용해 보십시오!