我得到了一个仅由 's','t','u','v' 作为字符组成的字符串 T。我想找到长度为 |T| 的字符串数它最多与 T 不同 n 个位置。而且每个这样的字符串在三个不同的位置不能有相同的字符,这些位置由相同的距离分隔。我的方法是使用动态编程方法,使得 dp[i][j][k] 表示长度为 i 的此类字符串的数量,在 j 位置不同而在第 k 个字符结束,其中 k=s,t,u,v 。
if(k在T的第i个字符相同)
dp[i][j][k]=dp[i-1][j][0]+dp[i-1][j][1]+dp[i-1][j][ 2]-(由于在第i个位置添加了k并且违反了相同分隔距离的条件而额外的字符串)
但我知道这是错误的?
例如,假设 T ='sstt' 并且我们必须找到最多 2 个位置不同的字符串,然后在三个不同位置以相同距离分隔的不具有相同字符的字符串是 'tstt'、'ssts' 和等等
最佳答案
这看起来真的很有趣。或许您可以枚举两对的数量,然后继续计算?
关于string - 最多 n 个位置不同的字符串数?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/36518705/