Pythonで同じサイズの文字列を見つけるプログラム

小文字と別の整数「j」で構成される文字列「i」があるとします。 'i'のサイズに等しく、辞書式に'i'に等しく、'j'より大きい連続した等しい文字がない文字列がいくつあるかを調べる必要があります。

答えは、Modの結果を10 ^ 9+7で見つけることによって計算する必要があります。

したがって、入力がi ="app"、j =2の場合、出力は405になります。

これを解決するには、次の手順に従います-

• j <=0の場合、

  • 0を返す

• m：=10 ^ 9 + 7

• n：=iのサイズ

• nums：=sに存在する各文字の（文字のUnicode表現-「a」のUnicode表現）を含む新しいリスト

• dp（0、True、-1、0）mod m

  を返します

• 関数dp（）を定義します。これには、pos、bound、last、countが必要です

  • count> jがゼロ以外の場合、

    • 0を返す

  • posがnと同じ場合、

    • 1を返す

  • num：=nums [pos]

  • res：=0

  • 0から（バインドされている場合はnum + 1、それ以外の場合は26）の範囲のiの場合、実行します

    • res：=res + dp（pos + 1、バインドされ、iがnum、i、countと同じ場合はtrue *（iがlastと同じ場合はtrue）+ 1）

  • 解像度を返す

• メインメソッドからreturndp（0、True、-1、0）％m

例

理解を深めるために、次の実装を見てみましょう-

class Solution:
   def solve(self, s, k):
      if k <= 0:
         return 0
      MOD = 10 ** 9 + 7
      n = len(s)
      nums = [ord(char) - ord("a") for char in s]
      def dp(pos, bound, last, count):
         if count > k:
            return 0
         if pos == n:
            return 1
         num = nums[pos]
         res = 0
         for i in range(num + 1 if bound else 26):
            res += dp(pos + 1, bound and i == num, i, count * (i == last) + 1)
         return res
      return dp(0, True, -1, 0) % MOD
ob = Solution()
print(ob.solve('app',2))

入力

i = "app"
j = 2

出力

405