回文チェック — JS (3 日目)

8343 ワード
javascript programming palindrome problemsolving テキストリンク

回文チェック



問題を理解する



与えられた文字列が回文であるかどうか、つまり、与えられた文字列が前方と後方を同じように読み取るかどうかを判断する関数を作成します.

アプローチ 1: 2 つの指針



回文である次の文字列があるとします.

racecar


文字列の最初の文字が最後の文字と等しく、2 番目の文字が最後から 2 番目の文字と等しいことがわかります.ただし、中央の文字は除きます.だから私たちはできる
文字列の先頭と末尾の両方から中央に移動し、すべての文字を他の文字と比較することによって、文字列が回文であるかどうかを判断します.不一致なしで中間文字に到達した場合、文字列は回文です.
  • 2 つのポインター left と right をそれぞれ文字列の最初のインデックスと文字列の最後のインデックスに初期化します.

  • 左のポインターが右のポインターの前に来る間、
  • 2 つのポインターが指している文字を比較します.それらが同じでない場合は、 false を返します.
    それ以外の場合は、左のポインターを右に、右のポインターを左に移動します.

  • false を返さずにループが終了した場合、不一致がないことを意味するため、文字列は回文であり、 true を返します.

    • 時間と空間の複雑さ


  • 反復: O(n) 時間 | O(1) スペース.n は文字列の長さです.
  • 再帰: O(n) 時間 | O(n) スペース.n は文字列の長さです.

    • 反復解法



    function isPalindrome(string) {
  let leftIdx = 0;
  let rightIdx = string.length - 1;

  while (leftIdx < rightIdx) {
    if (string[leftIdx] !== string[rightIdx]) return false;

    leftIdx++;
    rightIdx--;
  }

  return true;
}

    再帰的な解決策



    function isPalindrome(string, leftIdx = 0) {
  const rightIdx = string.length - 1 - leftIdx;

  if (leftIdx >= rightIdx) return true;

  return (
    string[leftIdx] === string[rightIdx] && isPalindrome(string, leftIdx + 1)
  );
}

    アプローチ 2: ブルート フォース



    文字列が回文の場合、逆バージョンの文字列は元の文字列と同じです.

    "racecar"
reversed: "racecar"

"hello"
reversed: "olleh"


    したがって、文字列が回文かどうかを判断するには、入力文字列を逆にして元の文字列と比較するだけです.

    時間と空間の複雑さ


  • 入力文字列の逆バージョンを文字列として保存: O(n^2) 時間 | O(n) スペース.n は文字列の長さです. O(n^2) 時間かかる理由は、ほとんどのプログラミング言語で文字列が
    不変です.文字列に文字を追加する場合、O(n) 操作である新しい文字列を作成する必要があります.長さ n の文字列の逆バージョンを作成するには、n 文字を逆文字列に追加します.したがって、全体の時間計算量は O(n^2) です.
  • 配列を使用して反転文字列を格納する:
    O(n) 時間 | O(n) スペース.n は文字列の長さです.

    • 文字列を使用したソリューション




    function isPalindrome(string) {
  let reversedString = '';

  for (let i = string.length - 1; i >= 0; i--) {
    reversedString += string[i];
  }

  return reversedString === string;
}


    アレイを使用したソリューション




    function isPalindrome(string) {
  const reversedChars = [];

  for (let i = string.length - 1; i >= 0; i--) {
    reversedChars.push(string[i]);
  }

  return reversedChars.join('') === string;
}


    別の簡単な解決策




    var palindrome = string => string == string.split('').reverse().join('')


    皆さんが定期的に更新されることを願っています.次の投稿でお会いしましょう.

    このシリーズの Github リポジトリ: daily-problem-solving-js

    参照:
  • pinglu85
    • 【Visual Studio】リンカーの設定一つでたった 11行 のプログラムがコンパイルできなかった話
    Rshinyでグラフの大きさをユーザーが指定できるように＆グラフの描画をボタン押下時のみに。change plot size by user input