Pythonで非共有単語の最大長を見つけるプログラム

単語と呼ばれる小文字のアルファベット文字列のリストがあるとすると、共通の文字を共有しない2つの異なる単語の長さの最大合計を見つける必要があります。したがって、入力がwords =["abcd"、 "mno "、" abdcmno "、" amno "]の場合、単語は共通の文字を共有しないため、出力は7になります[" abcd "、" mno "]、全長は7です。

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

• 関数sign（）を定義します。これには言葉が必要です
• 値：=0
• 単語のcごとに、
  • value：=value OR（2 ^（ASCII of c-ASCII of'a'））
• 戻り値
• メインの方法から、次の手順を実行します
• signature：=単語内の各xのsign（x）を含むリスト
• ans：=0
• 0から単語のサイズまでの範囲のiについては、
  • i + 1から単語のサイズまでの範囲のjについては、
    • signature [i] ANDsignature [j]が0と同じ場合、
      • ans：=ansの最大値と単語のサイズ[i]+単語のサイズ[j]
• 回答を返す

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

例

class Solution:
   def sign(self, word):
      value = 0
      for c in word:
         value = value | (1 << (ord(c) - 97))
      return value
   def solve(self, words):
      signature = [self.sign(x) for x in words]
      ans = 0
      for i in range(len(words)):
         for j in range(i + 1, len(words)):
            if signature[i] & signature[j] == 0:
               ans = max(ans, len(words[i]) + len(words[j]))
      return ans
ob = Solution()
words = ["abcd", "mno", "abdcmno", "amno"]
print(ob.solve(words))

入力

["abcd", "mno", "abdcmno", "amno"]

出力

7