首页 文章

使用std :: map检查字符串是否包含重复项

提问于
浏览 次
1

我有一个函数，通过将每个char作为键来检查字符串是否包含使用std :: map的重复项 . 无法弄清楚为什么这不起作用 .

#include<iostream>
#include<map>
#include<string>
int unique_char(std::string s){
 for(int i=0 ; i < s.size(); i++ )
  {
    std::map<char,int> uniq_hash_table;
    std::pair<std::map<char,int>::iterator,bool> ret;
    ret = uniq_hash_table.insert(std::pair<char,int>(s[i],0));
    if(ret.second==false)
     {
      std::cout << "The string contains duplicates" << std::endl;
      return 1;
     }
  }
return 0;
}
int main()
{
 std::string s="abcd";
 std::string s1="aabc";
 if(unique_char(s)==0){
 std::cout << "The 1st string does not contain duplicates" << std::endl;}
 if(unique_char(s1)==0){
 std::cout << "The 2nd string does not contain duplicates" << std::endl;}
 return 0;
}

对于这两个示例，程序返回“字符串不包含重复项” .

ps：我故意使用std :: map来获得O（n）解决方案 .

c++ string dictionary

3 回答

  • 1

    它不起作用，因为 uniq_hash_table 为 for 循环内的每个符号重新创建 .

    尝试在 for 循环之前将其移动到函数的开头：

    std::map<char,int> uniq_hash_table;

for(int i=0 ; i < s.size(); i++ )
{
    // ...
}
    回复于
  • 1

    由于 Map 定义位于for循环的主体内，因此在每次迭代时都会重新创建一个空 Map .

    在循环外声明你的容器，它会更好地工作 .

    请注意，如果从不增加int值，则可以使用set而不是map .

    回复于
  • 2

    您的解决方案不起作用，因为在循环的每次迭代中都会重新创建 std::map<char,int> . 然后，在循环的每次迭代中，映射为空 . 然后，没有重复 .

    最好使用 std::set<char> . 你可以这样做：

    bool contains_duplicated_char(const std::string& s)
{
  std::set<char> check_uniq;
  for(unsigned long int i = 0; i < s.length(); ++i)
    if(!check_uniq.insert(s[i]).second)
      return true; // Duplicated char found
  return false; // No duplicated char found
}

    然后通过这种方式调用它：

    const std::string str = "abcdefghijklamnopb";
const bool dupl = contains_duplicated(str);

    为了使您的代码更通用（管理更多数据类型），您还可以通过以下方式创建函数：

    template <typename Type, typename IteratorType>
bool contains_duplicated(IteratorType begin, IteratorType end)
{
  std::set<Type> check_uniq;
  for(IteratorType it = begin; it != end; ++it)
    if(!check_uniq.insert(*it).second)
      return true;
  return false;
}

    然后称之为：

    std::vector<std::string> vec_str;
vec_str.push_back("Foo");
vec_str.push_back("Bar");
vec_str.push_back("Baz");
vec_str.push_back("Bar");
const bool dupl = contains_duplaicated<std::string>(vec_str.begin(), vec_str.end());
//...
const std::string str = "abcdefab";
const bool dupl2 = contains_duplacated<char>(str.begin(), str.end());
//...
const std::deque<long int> x(4, 0);
x[0] = 1;
x[1] = 17;
x[2] = 31;
x[3] = 0;
const bool dupl3 = contains_duplicated<long int>(x.begin(), x.end());
    回复于

相关问题