Pythonで指定された条件を満たす辞書式最小の文字列を見つけます

n個の数値の配列Aがあるとします。ここで、A [i]は、文字列sの長さ（i + 1）のプレフィックス内の個別の文字の数を示します。指定されたプレフィックス配列を満たす辞書式最小の文字列を見つけます。すべての文字は小文字の英語のアルファベット[a-z]になります。そのような文字列がない場合は、-1を返します。

したがって、入力がA =[1,1,2,3,4]の場合、prefix [0]には1つの異なる文字があり、prefix [1]には1つの異なる文字、prefix [2]があるため、出力はaabcdになります。 2つの異なる文字があり、prefix [3]には3つの異なる文字があり、prefix [4]には4つの異なる文字があり、文字列が最小です。

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

• n：=Aのサイズ

• 文字：='a'

• 文字列：=空白の文字列

• n <1またはA[0]が1でない場合、

  • -1を返す

• string：=文字列連結文字

• 文字：=この現在の文字の次の文字

• 1からnの範囲のiの場合、実行します

  • 違い：=A [i]-A [i-1]

  • 差>1または差<0またはA[i]>26の場合、

    • -1を返す

  • それ以外の場合、差が0と同じ場合、

    • string：=string concatenate'a'

  • それ以外の場合

    • string：=文字列連結文字

    • 文字：=この現在の文字の次の文字

• 文字列を返す

例

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

def get_smallest_string(A):
   n = len(A)
   character = 'a'
   string = ""
   if (n < 1 or A[0] != 1):
      return -1
   string += str(character)
   character = chr(ord(character) + 1)
   for i in range(1, n):
      difference = A[i] - A[i - 1]
      if (difference > 1 or difference < 0 or A[i] > 26):
         return -1
      elif (difference == 0):
         string += 'a'
      else:
         string += character
         character = chr(ord(character) + 1)
return string

A = [1, 1, 2, 3, 4]
print(get_smallest_string(A))

入力

[1, 1, 2, 3, 4]

出力

aabcd