毎日のアルゴリズム: 回文部分文字列

[[434467]]

文字列が与えられた場合、その文字列に含まれる回文の部分文字列の数を数えることがタスクです。

開始位置または終了位置が異なる部分文字列は、同じ文字で構成されていても、異なる部分文字列と見なされます。

例1:

入力: "abc"   
 
出力: 3 
 
説明: 3 つの回文部分文字列: "a" 、 "b" 、 "c"

例2:

入力: 「aaa」   
 
出力: 6 
 
説明: 6 つの回文部分文字列: "a" 、 "a" 、 "a" 、 "aa" 、 "aa" 、 "aaa"

ヒント：

入力文字列の長さは 1000 を超えません。

解決策1: ブルートフォース

countSubstrings =関数(s) {
  カウントを 0 にする
( i = 0 とします; i < s.length; i++) {
 (j = i; j < s.length; j++)の場合{
      if (isPalindrome( s.substring (i, j + 1))) {
カウント++
      }
    }
  }
戻る カウント 
 } 
 
 let isPalindrome =関数(s) {
  i = 0、j = s.length - 1 とします。
  i < j である間 {
    s[i] != s[j] の場合、戻り値 間違い 
    私は++
    じ --  
  }
戻る 真実 
 }

複雑性分析:

時間計算量: O(n3)
空間計算量: O(1)

解決策2: 動的プログラミング

文字列の最初と最後の文字が同じで、残りの部分文字列も回文である場合、その文字列は回文です。その中で、残りの部分文字列が回文であるかどうかはより小さなサブ問題であり、その結果はより大きな問題の結果に影響を与えます。

サブ問題をどのように記述するのでしょうか?

明らかに、部分文字列は両端の i ポインタと j ポインタによって決定されます。これらは部分問題を記述する変数です。部分文字列 s[i...j] (dp[i][j]) が回文であるかどうかが部分問題です。

計算されたサブ問題の結果は、基本ケースから始めて 2 次元配列に記録し、表に記入するように各サブ問題の解を導出します。

    じ
    ああ、ああ、ああ
私は✅
  ✅
  b ✅
  ✅

注: i<=j、テーブルの半分だけ使用すればよく、垂直にスキャンする

それで：

 i === j: dp[i][j] =真 
 j - i == 1 && s[i] == s[j]: dp[i][j] =真 
 j - i > 1 && s[i] == s[j] && dp[i + 1][j - 1]: dp[i][j] =真

今すぐ：

 s[i] == s[j] && (j - i <= 1 || dp[i + 1][j - 1]): dp[i][j] =真

そうでなければ偽

コード実装:

 countSubstrings =関数(s) {
  定数len = s.length
  カウントを 0 にする
  const dp = 新しい配列(len) 
 
 (i = 0; i < len; i++)の場合{
    dp[i] = 新しい配列(len).fill( false )
  }
 (j = 0; j < len; j++)の場合{
 ( i = 0; i <= j; i++ とします) {
      s[i] == s[j] && (j - i <= 1 || dp[i + 1][j - 1]) の場合 {
        dp[i][j] =真 
カウント++
      }それ以外{
        dp[i][j] =偽 
      }
    }
  }
戻る カウント 
 }

コード実装（最適化）：

上記の表の縦の列を 1 次元配列として考えるか、縦にスキャンします。この場合、dp を 1 次元配列として定義するだけで済みます。

 countSubstrings =関数(s) {
  定数len = s.length
  カウントを 0 にする
  const dp = 新しい配列(len) 
 
 (j = 0; j < len; j++)の場合{
 ( i = 0; i <= j; i++ とします) {
      s[i] === s[j] && (j - i <= 1 || dp[i + 1]) の場合 {
        dp[i] =真 
カウント++
      }それ以外{
        dp[i] =偽 
      }
    }
  }
戻る カウント;
 }