palindromeを検証する方法

文字列str , 返されるメソッドを記述できますかTrue パラリンドロームならばFalse そうでなければ?あなたが思い出すならばpalindrome は、「フォワードと同じ後方を読むA単語、句またはシーケンス」と定義されます.今のところ、特殊文字や空白を含む入力文字列を持たないと仮定します.

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

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

余分な挑戦のために、非英数字文字を無視しようとします.我々が示す最終的な解決はすべての端ケースを扱います.
このレッスンは、もともと2007年に出版されましたhttps://algodaily.com , 私は技術的なインタビューコースを維持し、野心的な開発者のために考える作品を書く.

trueまたはfalse？

ストリングの反転が元のストリングに等しいならば、ストリングはpalindromeとして定義されます.
例えば、「toot」はpalindromeです、しかし、「ブート」はそうではありません.
真実は
これは古典的な質問です、そして、解決する複数の方法があります.学習のために、それらのすべてをカバーしましょう!

組み込みメソッドの使用

これはおそらく実際のインタビューでは無効ですが、あなたは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'));

順序

ストリングがpalindromeであるならば、うまくわかることは、何を注文しますか?

lowループがhighより小さい間に実行するwhileループを開く

ループの最後まで続け、真を返す

つの変数を定義します.

` string [ low ] `が` string [ high ] `と等しくない場合、falseを返します.インクリメント・ロー

解決方法

ループの最後まで続け、真を返す

` string [ low ] `が` string [ high ] `と等しくない場合、falseを返します.インクリメント・ロー

lowループがhighより小さい間に実行するwhileループを開く

つの変数を定義します.

複数選択

次の擬似コードは入力文字列に何をしますか?

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 反復.文字列をその端から単純に繰り返すただ一つのポインタを使う代わりに、なぜ2を使用しないのですか?

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'));

上記の作業は2つのポインタを指定することです.start and 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 !