連結がPythonのターゲットと同じサブシーケンスの最小数を見つけるプログラム

sourceとtargetの2つの文字列があるとすると、それらを連結した場合にtargetと同じになるように、作成できるsourceのサブシーケンスの最小数を見つける必要があります。そのような結果がない場合は、-1を返します。

したがって、入力がsource ="xyz" target ="xyzyzz"のようである場合、これらの["xyz" + "yz" + "z"]

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

• s_size：=sのサイズ、t_size：=tのサイズ
• concat_count：=0、target_idx：=0
• target_idx
• source_idx：=0
• temp_index：=target_idx
• source_idx
• s[source_idx]がt[target_idx]と同じ場合、
  • target_idx：=target_idx + 1
• source_idx：=source_idx + 1

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

例

class Solution:
   def solve(self, s, t):
      s_size, t_size = len(s), len(t)
      concat_count = 0
      target_idx = 0
      while target_idx < t_size:
         source_idx = 0
         temp_index = target_idx

         while source_idx < s_size and target_idx < t_size:
            if s[source_idx] == t[target_idx]:
               target_idx += 1
            source_idx += 1

         if temp_index == target_idx:
            return -1
         concat_count += 1
      return concat_count
ob = Solution()
source = "xyz"
target = "xyzyzz"
print(ob.solve(source, target))

入力

"xyz", "xyzyzz"

出力

3