Python 程序将字符串拆分为 k 个不同的分区

假设我们有一个字符串 s 和一个值 k。k 的值是 s 长度的因子，假设长度为 n。我们可以将 s 拆分为 n/k 个不同的子字符串，称为大小为 k 的 t_i。然后使用这些 t_i 生成 u_i，使得

  • u_i 中存在的字符是 t_i 中字符的子序列

  • 从这些字符串中删除任何重复的字符，使得 u_i 中每个字符的频率为 1

我们必须找到这些 u_i 字符串

因此，如果输入类似于 s = "MMPQMMMRM" k = 3，则输出将为 ["MP", "QM", "MR"]，因为 s 的大小为 9，k 为 3，所以 9/3 = 3。字符串为 MMP、QMM 和 MRM，但由于我们不支持重复字符，因此它们将为 MP、QM 和 MR。

为了解决这个问题，我们将遵循以下步骤：

  • i := 0
  • ret := 一个新的列表
  • mp := 一个新的映射
  • to_print := 空字符串
  • 当 i < s 的大小时，执行以下操作：
    • 如果 i mod k 与 0 相同，并且 i 不为 0，则
      • 将 to_print 插入 ret 的末尾
      • 清空 mp 和 to_print
    • 如果 s[i] 不存在于 mp 中，则
      • mp[s[i]] := 0
      • to_print := to_print + s[i]
    • i := i + 1
  • 将 to_print 插入 ret 的末尾
  • 返回 ret

示例

让我们看看以下实现以更好地理解

def solve(s, k):
   i = 0
   ret = []
   mp, to_print = {}, ""
   while i < len(s):
      if i % k == 0 and i != 0:
         ret.append(to_print)
         mp, to_print = {}, ""
      if s[i] not in mp.keys():
         mp[s[i]] = 0
         to_print += s[i]
      i += 1
   ret.append(to_print)
   return ret

s = "MMPQMMMRM"
k = 3
print(solve(s, k))

输入

"MMPQMMMRM", 3

输出

['MP', 'QM', 'MR']

更新于: 2021年10月12日

482 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始
广告