string - 准备字符串中的重复字符 - 算法

Question

给定三个字符串 a、b 和 c。递归地尝试检查 c 是否是 a 和 b 的穿插版本。

举个例子。

a = dolphin
b = whale
c = dolwhphialne

您可以看到 c 字符串中的字符与它们在原始字符串中的顺序相同，只是打乱了一点点。

我正在研究的算法是。

Algorithm: stringOrderedCheck(a,b,c)
    n:= length of a
    m:= length of b
    nm:= length of a and b
    if (nm > 0) then
        if(first letter of a equals first letter of c) then
            return stringOrderedCheck(a without first letter,b, c without first letter)
        else if(first letter of b equals first letter of c) then
            return stringOrderedCheck(a,b without first letter, c without first letter)
    else 
        return false;

但我遇到的问题是这样的，例如:

a = yyyyb
b = yyyx
c = yyyyxyyyb

如何准备函数以实现它需要从 a 中获取第一个字母这是 y然后从 b 中取出下一个 4这是 yyyx .

重复值给我带来了一个大问题。

当 a 中的两个字符都出现时，我需要做一些事情和 b等于 c 中的字符

Answer 1

我认为这里的主要问题是，在这一点上，您的路径可以分成两个单独的递归调用，即树划分而不是更深。问题是，由于您的 else if，只有在第一条路径不存在的情况下才会考虑第二条路径，即，它从不考虑两条路径。然后你可以为此做准备:

#your original code
if(first letter of a equals first letter of c) then
        return stringOrderedCheck(a without first letter,b, c without first letter)
else if(first letter of b equals first letter of c) then
        return stringOrderedCheck(a,b without first letter, c without first letter)

你可以把它改成:

if(first letter of a equals first letter of c) then
    if(first letter of b equals first letter of c) then
        return stringOrderedCheck(a without first letter,b, c without first letter) OR stringOrderedCheck(a,b without first letter, c without first letter)
    else
        return stringOrderedCheck(a without first letter,b, c without first letter)
else if(first letter of b equals first letter of c) then
        return stringOrderedCheck(a,b without first letter, c without first letter)

这样无论第一个条件如何，它都会检查两个。

您还可以通过在 if 检查之前将 bool 保存为变量然后断言一般或:

valid:= false
if(first letter of a equals first letter of c) then
        valid = valid or stringOrderedCheck(a without first letter,b, c without first letter)
if(first letter of b equals first letter of c) then #take out the else so it will always check
        valid = valid or stringOrderedCheck(a,b without first letter, c without first letter)
return valid

最后一个解决方案显示了一个非常重要的注意事项:确保在返回 false 的 if/else if 语句之后有一个 else(如果你不使用最后一个解决方案)来说明 c 的第一个字母是否直接向上无效(即不是 a 或 b 的第一个字母)