c++ - 来自另一个 bool 函数的一个字符

Question

我想要一个函数，当且仅当可以通过简单地划掉某些字母来从 char* t 获得 char* s 时，该函数才会返回 true，例如g("ERT", "EAARYT")=true 和 g("ERT","ABCT")=false。

我对此代码的想法如下:

bool g(char* s, char* t) {
    for (int i=0; s[i]!=0;i++) {
        for (int j=i; t[j]!=0; j++) {
            if (s[i]==t[j]) {
                return true;
            }
        }
    }
    return false;
}

显然它不起作用，因为它只检查第一个字母是否存在，然后立即返回 true。 我应该如何改变它？

我更喜欢使用嵌套循环/if 结构，这应该是可行的。

Answer 1

当且仅当可以通过简单地划掉某些字母从 char *t 获得 char *s 时返回 true。这意味着两件事:

• [A] t 应包含 s 的所有字符。因此，我们需要存储字符数。
• [B] t 应包含 s 的所有字符，并且 t 应具有与 顺序相同的公共(public)字符s。

解决方案 A:t 中的字符顺序并不重要。重要的是 s 中的所有字符都应该出现在 t 中。

g("ERRT", "ERT") = false

g("ERRR", "ERRT") = false

g("ERRR", "RRRE") = true

bool g(char* s, char* t) 
{
    int hash[256] = {0};
    int i;
    for(i = 0; t[i]; ++i) 
    {
        hash[t[i]] += 1;
    }

    for(i = 0; s[i]; ++i) 
    {
        if(hash[s[i]] <= 0)
        {
            return false;
        }
        else
        {
            hash[s[i]] -= 1;
        }
    }

    return true;
}

解决方案 B:t 中的字符顺序确实很重要。此外，s 中的所有字符都应出现在 t 中。

g("ERRT", "RERT") = false

g("ERRR", "RRER") = false

g("ERRR", "RRRE") = false

g("ERTR", "RERGRTBR") = true

bool g(char* s, char* t) 
{
    if(strcmp(LCS(s, t), s) == 0)
    {
        return true;
    }

    return false;
}    

其中，LCS(s, t) = Longest Common Subsequence