0

我今天有期中考试。这是第一个问题。我无法解决这个问题。确切的要求如下：我们必须确定一个字符串，比如说“DA”是否是另一个“ABCD”的子集。字母的数量至关重要，例如“DAD”不是“ABCD”的子集。因为“D”重复了两次，而在父字符串中“D”出现了一次。也可以假设没有。父字符串的字母数总是等于或大于另一个。

我想了很多。我对此的方法是，我会将要找到的子字符串的字符与父字符串进行比较。如果找到匹配项，我会将其索引存储在第三个数组中。所以最后我将拥有父数组的字符数组，该数组与另一个数组中的字符匹配。这就是我能够达到的程度。

#include <iostream>
#include <cstring>
using namespace std;

int main()
{
char array[] = "ABCD";
char array1[] = "AB";

int size = strlen(array);
int size1 = strlen(array1);

int temp[size];
int no = 0;
for (int i = 0; i< size1; i++)
        {
        for (int j = 0; j< size; j++)
                {
                if  (array1[i]==array[j])
                        {
                        for(int k = 0; k<size ; k++)
                                {
                                if (temp[k] != j)
                                        {
                                        temp[no] = j;
                                        no++;
                                        }
                                }
                        }
                }
        }

for (int i = 0; i<size; i++)
cout<<endl<<temp[i]<<" ";
return 0;
}

请帮助解决这个问题，如果您有其他方法，请告诉我。此外，数组或字符串是否是解决此问题的更好方法。我正在用 C++ 编写，在此先感谢

4

2 回答 2

1

（我最近将此作为我学生的测验，但我们使用的是 Groovy 和 Java。）

一个简单的方法"ABCD"：创建字符串（"_BC_"”。

于 2012-10-05T17:00:44.063 回答
0

您还可以计算每个字符串中每个字母的出现次数，并确保第二个字符串中每个字母的计数小于或等于第一个字符串中每个字母的计数。如果您想将多个潜在子字符串与单个字母集合进行比较（例如，将字典中的所有单词与 Boggle 中的当前字母进行比较），这可能会更好。

这段代码将做到这一点。它的主要限制是它仅适用于包含英文字母表中 26 个大写字母的字符串。但它传达了这个想法。

#include <iostream>
#include <cstring>
using namespace std;

void stringToArray(char *theString, int *countArray) {
    int stringLength = strlen(theString);
    for (int i=0; i<26; i++) {
        countArray[i] = 0;
    }
    for (int i=0; i<stringLength; i++) {
        countArray[theString[i] - 'A']++;
    }
}

bool arrayIsSubset(int *superCount, int *subCount) {
    //returns true if subCount is a subset of superCount
    bool isSubset = true;
    for (int i=0; i<26 && isSubset; i++) {
        isSubset = subCount[i] <= superCount[i];
    }
    return isSubset;
}

int main()
{
    char array[] = "ABCD";
    char array1[] = "AB";
    char array2[] = "ABB";

    int letterCount[26], letterCount1[26], letterCount2[26];

    stringToArray(array, letterCount);
    stringToArray(array1, letterCount1);
    stringToArray(array2, letterCount2);

    cout << "array1 is " << (arrayIsSubset(letterCount, letterCount1) ? "" : "not ") << "a subset" << endl;
    cout << "array2 is " << (arrayIsSubset(letterCount, letterCount2) ? "" : "not ") << "a subset" << endl;
}

产生：

array1 is a subset
array2 is not a subset
于 2012-12-07T00:40:01.253 回答