c - 修改堆栈中字符串的算法

Question

我正在处理堆栈问题。我有一个字符串。每个字母激活入栈，每个 * 激活出栈。

例如

T_I**_MA***SB*E***

获取输出I_AM_BEST。

我想创建一个算法来找出是否可以向两个给定字符串中的任何一个添加星号 (*) 以重新创建另一个字符串。

例如，我有 2 个字符串 s1 和 s2 作为输入。

s1 = "hello"
s2 = "lle"

算法查看 s1 并验证我可以从字符串 1 中弹出字符串 2。所以它从字符串 1 给我输出 hell***o。

但是，我无法从 s2 创建 s1，因为我错过了字母 h 和 o。

现在我的努力是找到进行所有比较的有效方法，因为我需要检查所有字母和顺序。

如果有人愿意帮助我，我将不胜感激。也可以随时向我询问更多信息。

Here 是我目前的代码。

编辑:感谢大家的一些非常好的想法，他们让我继续前进，我终于用这个递归破解了它。只是一个肮脏的工作版本。到目前为止它似乎在工作:)

char global[40];

void rec(char s1[], char s2[], int b, int l, int count, int cur_count)
{
    if(l >= strlen(s2) || b > strlen(s1))
        return;

    if(cur_count >= count) {
        global[strlen(global)] = s2[l];
        count++;
    }

    if(s1[b] == s2[l])
    {
        global[strlen(global)] = '*';
        rec(s1,s2,++b,0,count,0);
    }
    else {
        rec(s1,s2,b,++l,count,++cur_count);
    }

}


void findString()
{
    char s1[] = "123456";
    char s2[] = "531246";

    rec(s1,s2,0,0,0,0);
    int i = 0;
    for(i=0;i<strlen(global);i++)
        printf("%c",global[i]);

}

Answer 1

我会尝试这种方法:

用一个字符串来表示栈——称之为st

所以基本思路是:

while(s1 not empty)
{
    if (st[0] == s2[0])
    {
        // result += '*'
        // pop 
        // remove s2[0]
    }
    else if if (s1[0] == s2[0])
    {
        // result += s1[0] + '*'
        // push
        // pop
        // remove s1[0]
        // remove s2[0]
    }
    else
    {
        // result += s1[0]
        // push
        // remove s1[0]
     }
}

该方法的工作方式如下:

// Initialization
st = ""         // stack - push and pop is done on st[0]
s1 = "hello"
s2 = "lle"
result = ""

// Stack empty -> do nothing
// s1[0] != s2[0] -> just push s1[0] and remove it from s1
st = "h"
s1 = "ello"
s2 = "lle"
result = "h"

// st[0] != s2[0] -> do nothing
// s1[0] != s2[0] -> just push s1[0] and remove it from s1
st = "eh"
s1 = "llo"
s2 = "lle"
result = "he"

// st[0] != s2[0] -> do nothing
// s1[0] == s2[0] -> push and pop s1[0] and remove it from s1 and remove s2[0] 
st = "eh"
s1 = "lo"
s2 = "le"
result = "hel*"

// st[0] != s2[0] -> do nothing
// s1[0] == s2[0] -> push and pop s1[0] and remove it from s1 and remove s2[0] 
st = "eh"
s1 = "o"
s2 = "e"
result = "hel*l*"

// st[0] == s2[0] -> pop and remove s2[0]
st = "h"
s1 = "o"
s2 = ""
result = "hel*l**"

// s2 empty -> just push the rest of s1
st = "oh"
s1 = ""
s2 = ""
result = "hel*l**o"

请注意，我得到的字符串 "hel*l**o 与您的示例(即 hell***o)不同，但它仍然会生成正确的输出.