计算组成字符串的方法数

Question

我刚刚开始学习动态规划，并且能够做一些基本的问题，例如斐波那契、背包和其他一些问题。遇到问题在下面，我卡住了，不知道如何继续前进。让我感到困惑的是，在这种情况下，基本情况是什么，以及重叠的问题。不知道这使我无法发展关系。它们在这个例子中不像在我目前已经解决的之前的例子中那么明显。

Suppose we are given some string origString, a string toMatch and some number maxNum greater than or equal to 0. How can we count in how many ways it is possible to take maxNum number of nonempty and nonoverlapping substrings of the string origString to make up the string toMatch?

Example:

If origString = "ppkpke", and toMatch = "ppke"

maxNum = 1: countWays("ppkpke", "ppke", 1) will give 0 because toMatch is not a substring of origString.

maxNum = 2: countWays("ppkpke", "ppke", 2) will give 4 because 4 different combinations of 2 substring made up of "ppkpke" can make "ppke". Those strings are "ppk" & "e", "pp" & "ke" , "p" & "pke" (excluding "p") and "p" & "pke" (excluding "k")

Answer 1

作为最初的警告，我会说虽然我的解决方案恰好与微型测试集的预期输出相匹配，但它很可能是错误的。由您根据您可能拥有的其他示例等进行仔细检查。

该算法遍历较长的字符串并尝试将较短的字符串散布在其上。算法的增量状态由 3 个元素的元组组成：

长字符串坐标i (origString[i] == toMatch[j])
短字符串坐标j (origString[i] == toMatch[j])
我们进入那种状态的方式有多少种^^^

然后我们只是一遍又一遍地沿着字符串走，使用存储的、以前发现的状态，然后总结每个状态的实现方式的总数——以典型的动态编程方式。

对于一个算作解的状态，j必须在短字符串的末尾和动态算法的迭代次数必须相等到我们当时想要的子字符串的数量（因为每次迭代都会添加一个子字符串）。

从作业中我不完全清楚 maxNum 是否真的意味着像“exactNum”，即恰好那么多子串，或者我们是否应该对所有较小或相等的数字求和的子串。所以函数returns一个像{#substrings:#decompositions}这样的字典，这样就可以根据需要调整输出。

#!/usr/bin/env python

def countWays(origString, toMatch, maxNum):
  origLen = len(origString)
  matchLen = len(toMatch)
  state = {}
  for i in range(origLen):
    for j in range(matchLen):
      o = i + j
      if origString[o] != toMatch[j]:
        break
      state[(o, j)] = 1
  sums = {}
  for n in range(1, maxNum):
    if not state:
      break
    nextState = {}
    for istart, jstart in state:
      prev = state[(istart, jstart)]
      for i in range(istart + 1, origLen):
        for j in range(jstart + 1, matchLen):
          o = i + j - jstart - 1
          if origString[o] != toMatch[j]:
            break
          nextState[(o, j)] = prev + nextState.get((o, j), 0)
    sums[n] = sum(state[(i, j)] for i, j in state if j == matchLen - 1)
    state = nextState
  sums[maxNum] = sum(state[(i, j)] for i, j in state if j == matchLen - 1)
  return sums

result = countWays(origString='ppkpke', toMatch='ppke', maxNum=5)

print('for an exact number of substrings:', result)
print(' for up to a number of substrings:', {
  n: s for n, s in ((m, sum(result[k] for k in range(1, m + 1)))
                    for m in range(1, 1 + max(result.keys())))})

这个 ^^^ 代码是一个快速而丑陋的 hack，仅此而已。有很大的改进空间，包括（但不限于）生成器函数的使用（yield），@memoize的使用等。下面是一些输出：

for an exact number of substrings: {1: 0, 2: 4, 3: 8, 4: 4, 5: 0}
 for up to a number of substrings: {1: 0, 2: 4, 3: 12, 4: 16, 5: 16}

存储更多的动态状态（例如，为每个 n 保留它）然后重建并漂亮地打印（有效地）确切的，这将是一个有趣的（并且非常具有挑战性的）练习被计数的字符串（分解）组合。

Answer 2

这是一个递归的解决方案。

比较 source 和 target 的第一个字符，如果它们相等，则选择取它（在两个字符串中前进 1 个字符）或不取它（前进source 中有 1 个字符，但 target 中没有）。每次创建新的子字符串时，k 的值都会递减；还有一个额外的变量 continued 如果我们正在构建子字符串，则为 True，否则为 False。

def countWays(source, target, k, continued=False):
  if len(target) == 0:
    return (k == 0)
  elif (k == 0 and not continued) or len(source) == 0:
    return 0
  elif source[0] == target[0]:
    if continued:
      return countWays(source[1:], target[1:], k, True) + countWays(source[1:], target[1:], k-1, True) + countWays(source[1:], target, k, False)
    else:
      return countWays(source[1:], target[1:], k-1, True) + countWays(source[1:], target, k, False)
  else:
    return countWays(source[1:], target, k, False)

print(countWays('ppkpke', 'ppke', 1))
# 0
print(countWays('ppkpke', 'ppke', 2))
# 4
print(countWays('ppkpke', 'ppke', 3))
# 8
print(countWays('ppkpke', 'ppke', 4))
# 4
print(countWays('ppkpke', 'ppke', 5))
# 0

计算组成字符串的方法数

Counting the number of ways to make up a string

algorithm

dynamic-programming