在两个字符串中查找常见字符

我正在编码我们需要计算两个字符串中常见字符数的问题。 计数的主要部分是这样的

for(i=0; i < strlen(s1); i++) { for(j = 0; j < strlen(s2); j++) { if(s1[i] == s2[j]) { count++; s2[j] = '*'; break; } } } 

这与O(n ^ 2)逻辑一致。 但是,我想不出比这更好的解决方案。 任何人都可以用O(n)逻辑帮助我编码。

这很简单。 取两个int数组freq1freq2 。 将其所有元素初始化为0 。 然后读取字符串并将字符的频率存储到这些数组中。 之后比较数组freq1freq2以找到常见字符。

它可以在O(n)时间内以恒定的空间完成。

伪代码如下:

 int map1[26], map2[26]; int common_chars = 0; for c1 in string1: map1[c1]++; for c2 in string2: map2[c2]++; for i in 1 to 26: common_chars += min(map1[i], map2[i]); 

您当前的代码是O(n ^ 3),因为O(n) strlen s并产生不正确的结果,例如“aa”,“aa”(您的代码将返回4)。

此代码在O(n)中计算共同的字母(每个字母最多计算一次)。

 int common(const char *a, const char *b) { int table[256] = {0}; int result = 0; for (; *a; a++)table[*a]++; for (; *b; b++)result += (table[*b]-- > 0); return result; } 

根据您如何定义“共同字母”,您可能有不同的逻辑。 这是我正在使用的定义的一些测试用例(这是multiset交集的大小)。

 int main(int argc, char *argv[]) { struct { const char *a, *b; int want; } cases[] = { {"a", "a", 1}, {"a", "b", 0}, {"a", "aa", 1}, {"aa", "a", 1}, {"ccc", "cccc", 3}, {"aaa", "aaa", 3}, {"abc", "cba", 3}, {"aasa", "asad", 3}, }; int fail = 0; for (int i = 0; i < sizeof(cases) / sizeof(*cases); i++) { int got = common(cases[i].a, cases[i].b); if (got != cases[i].want) { fail = 1; printf("common(%s, %s) = %d, want %d\n", cases[i].a, cases[i].b, got, cases[i].want); } } return fail; } 

你可以用2n做到这一点:

 int i,j, len1 = strlen(s1), len2 = strlen(s2); unsigned char allChars[256] = { 0 }; int count = 0; for( i=0; i 

以下代码仅遍历每个sting一次。 所以复杂性是O(n)。 其中一个假设是上下案例被认为是相同的。

  #include int main() { char a[] = "Hello world"; char b[] = "woowrd"; int x[26] = {0}; int i; int index; for (i = 0; a[i] != '\0'; i++) { index = a[i] - 'a'; if (index > 26) { //capital char index = a[i] - 'A'; } x[index]++; } for (i = 0; b[i] != '\0'; i++) { index = b[i] - 'a'; if (index > 26) { //capital char index = b[i] - 'A'; } if (x[index] > 0) x[index] = -1; } printf("Common characters in '%s' and '%s' are ", a, b); for (i = 0; i < 26; i++) { if (x[i] < 0) printf("%c", 'a'+i); } printf("\n"); } 
 int count(string a, string b) { int i,c[26]={0},c1[26]={}; for(i=0;i 

这是更容易和更好的解决方案

 for (std::vector::iterator i = s1.begin(); i != s1.end(); ++i) { if (std::find(s2.begin(), s2.end(), *i) != s2.end()) { dest.push_back(*i); } } 

取自这里

C实现在O(n)时间和常量空间中运行。

 #define ALPHABETS_COUNT 26 int commonChars(char *s1, char *s2) { int c_count = 0, i; int arr1[ALPHABETS_COUNT] = {0}, arr2[ALPHABETS_COUNT] = {0}; /* Compute the number of occurances of each character */ while (*s1) arr1[*s1++-'a'] += 1; while (*s2) arr2[*s2++-'a'] += 1; /* Increment count based on match found */ for(i=0; iarr2[i] && arr2[i] != 0) c_count += arr2[i]; else if(arr2[i]>arr1[i] && arr1[i] != 0) c_count += arr1[i]; } return c_count; 

}

首先,您的代码不在O(n ^ 2)中运行,它以O(nm)运行,其中n和m是每个字符串的长度。

你可以在O(n + m)中完成,但不是更好,因为你必须经历每个字符串,至少一次,以查看一个字符是否同时存在。

C ++中的一个例子,假设:

  • ASCII字符
  • 包括所有字符(字母,数字,特殊,空格等……)
  • 区分大小写


 std::vector strIntersect(std::string const&s1, std::string const&s2){ std::vector presents(256, false); //Assuming ASCII std::vector intersection; for (auto c : s1) { presents[c] = true; } for (auto c : s2) { if (presents[c]){ intersection.push_back(c); presents[c] = false; } } return intersection; } int main() { std::vector result; std::string s1 = "El perro de San Roque no tiene rabo, porque Ramon Rodriguez se lo ha cortado"; std::string s2 = "Saint Roque's dog has no tail, because Ramon Rodriguez chopped it off"; //Expected: "S aint R oquesdghl , bcmrzp" result = strIntersect(s1, s2); for (auto c : result) { std::cout << c << " "; } std::cout << std::endl; return 0; } 

可以使用“捕获”的概念轻松完成,“捕获”是散列的子算法。