Python
 Computer >> コンピューター >  >> プログラミング >> Python

Pythonで文字を繰り返さない最長の部分文字列

文字列があるとします。文字を繰り返さずに最長の部分文字列を見つける必要があります。したがって、文字列が「ABCABCBB」のような場合、長さ3の繰り返しの部分文字列があるため、結果は3になります。これが「ABC」です。

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

  • set i：=0、j：=0、情報を保存するために1つのマップを設定します
  • ans：=0
  • whilej<文字列の長さs
    • s [j]がマップに存在しない場合、またはi> map [s [j]]の場合、
      • ans：=max（ans、j – i + 1）
      • map [s [j]]：=j
    • それ以外の場合
      • i：=map [s [j]] + 1
      • ans：=max（ans、j – i + 1）
      • jを1つ減らします
    • jを1増やします
  • 回答を返す
例（Python）

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

class Solution(object):
   def lengthOfLongestSubstring(self, s):
      i =0
      j = 0
      d={}
      ans = 0
      while j < len(s):
         if s[j] not in d or i>d[s[j]]:
            ans = max(ans,(j-i+1))
            d[s[j]] = j
         else:
            i = d[s[j]]+1
            ans = max(ans,(j-i+1))
            j-=1
         #print(ans)
         j+=1
      return ans
ob1 = Solution()
print(ob1.lengthOfLongestSubstring("ABCABCBB"))

入力

"ABCABCBB"

出力

3

  1. PythonのAscii（）

    ASCIIは、情報交換のための米国標準コードの省略形です。文字エンコード規格です。たとえば、英語のアルファベットAのASCII値は65です。Pythonは、オブジェクトの印刷可能な表現を取得するためにこの関数を提供します。これは、リスト、文字列、タプルなどのオブジェクトである1つのパラメーターを取ります。関数の出力は16進表現です。非ASCII文字は、\ x、\ u、または\Uエスケープを使用してエスケープできます。 構文 構文は-です。 Syntax: ascii(object) 例 個々の文字と複数の文字を含む文字列を印刷します。 # Individual Characters pri

  2. 最長の共通部分文字列に対するPythonのSequenceMatcher。

    2つの文字列が与えられた場合、私たちのタスクは最も長い共通のサブ文字列を出力することです。 SequenceMatcher.find_longest_match（）メソッドを使用してPythonの問題を解決します。 クラスdifflib.SequenceMatcherは、シーケンス要素がハッシュ可能である限り、任意のタイプのシーケンスのペアを比較するための柔軟なクラスです。 find_longest_match（a、x、b、y） a [a：x]とb [b：y]で最も長く一致するブロックを見つけます。 例 Input: str1 = pythonprogramming,