检查字符串中的唯一字符

Question

我正在尝试编写一段代码，用于检查字符串是否由唯一字符组成。在前几行进行了一些数据验证，并且输入符合这些条件的代码（长度=1或长度>36）是有效的。当我输入不符合先前规定要求的字符串时，我尝试将我的字符串的每个字符与其他每个字符进行比较。即使对于像以下示例中的唯一字符串一样的唯一字符的字符串，它也会返回该字符串不是由唯一字符组成的。

string string = "abcdefghijklmnopqrstuvwxyz0123456789";
bool uniqueCharacters = false;

//if length is 1, automatically return that the string is made up of unique characters
if (string.length() == 1) {
    uniqueCharacters = true;
}

 //there are 26 letters and 10 numbers, so if a string is made up of more than 36 chars, there must be some overlap
if (string.length() > 36) {
    uniqueCharacters = false;
}

else if (string.length() > 1 && string.length() < 37) {
    for (int i = 0; i < string.length(); i++) {
        for (int j = 1; j < string.length(); j++) {
            if (string[i] == string[j]) {
                uniqueCharacters = false;
            }
            else {uniqueCharacters = true;}
        }
    }
}

if (uniqueCharacters == true) {
    cout << "This string contains all unique characters \n";
}
if (uniqueCharacters == false) {
    cout << "This string does not contain all unique characters \n";
}

我认为这是一个逻辑错误，但是我无法找出问题所在。有什么想法吗？

- lottie3

---

解决这类问题的正确工具是调试器。在询问Stack Overflow之前，您应该逐行*查看您的代码。如需更多帮助，请阅读[如何调试小程序（Eric Lippert）]（https://ericlippert.com/2014/03/05/how-to-debug-small-programs/）。最少，您应该\[编辑]您的问题，以包括重现您的问题的[最小，完整和可验证的]示例，以及您在调试器中观察到的情况。 - πάντα ῥεῖ

int j = 1 应该改为 int j = i + 1。 - Jarod42

只是一个提示，尝试利用数据结构来降低算法的复杂度（大O）。 - nmargaritis

请注意，除非是为了解决编辑中指出的拼写错误，否则在提问后请勿更改代码。与您的问题相关，在这种有限的领域（char）中，一个值表可以在O（N）复杂度下解决您的问题。链接 - WhozCraig

我也同意 @πάνταῥεῖ 的观点 - 不是因为网站规则，而是因为你可以通过自己调试来学到更多。我们都曾经历过这种情况！ - Robbie

Answer 1

如果您只关心检查容器是否包含唯一的元素而不想对其进行排序，那么可以将数据复制到`std::set`中。`std::set`只存储唯一项目，因此一旦填充了该集合，如果大小与使用的容器不匹配，则知道存在重复项。

使用迭代器构造函数检查字符串是否只包含唯一元素就像这样简单：

std::string line = "abcdefghijklmnopqrstuvwxyz0123456789";
std::set<char> checker(line.begin(), line.end());
if (checker.size() != line.size())
    std::cout << "contains duplicates!"; 

- NathanOliver

Answer 2

bool uniqueCharacters = true; // <-- initialize to true then try to find if false

// We put the condition `uniqueCharacters` in the loop:
// no need to continue looping once we find a duplicate.
for (int i = 0; uniqueCharacters && i < string.length(); ++i) {
    for (int j = i+1; uniqueCharacters && j < string.length(); ++j) { // <-- start with j=i+1, to avoid checking a character versus itself
        if (string[i] == string[j]) {
            uniqueCharacters = false;
        }
    }
}

最后，请注意有专门用于重复管理的std工具，例如std::unique和std::set<>...

还要注意，您的算法并不是此任务的最快算法。

- A.S.H

Answer 3

你需要在以下位置中断循环：

if (string[i] == string[j]) {
    uniqueCharacters = false;
    // here you need to break the loop
}
else {uniqueCharacters = true;}

否则，在检测到非唯一值后，它可以被下一个循环迭代覆盖。

检查字符串唯一性的更简单的方法是使用算法中的std :: unique。

您还可以将每个字符移动到std :: set中，并检查字符串大小是否等于std :: set大小。

- paweldac

Answer 4

bool are_all_characters_unique(string str) {

    int n=str.length();
    std::sort(str.begin(),str.end());

    for(int i=0;i<n;i++){
        if(str[i]!=str[i++]){
            return false;
        }
        i++;

    }
    return true;
}

- Ayush Patidar

Answer 5

string string = "abcdefghijklmnopqrstuvwxyz0123456789";
bool uniqueCharacters = false;

//if length is 1, automatically return that the string is made up of unique characters
if (string.length() == 1) {
    uniqueCharacters = true;
}

 //there are 26 letters and 10 numbers, so if a string is made up of more than 36 chars, there must be some overlap
if (string.length() > 36) {
    uniqueCharacters = false;
}

else if (string.length() > 1 && string.length() < 37) {
    for (int i = 0; i < string.length(); i++) {
        for (int j = i+1; j < string.length(); j++) {
            if (string[i] == string[j]) {
                uniqueCharacters = false;
            }
            else {uniqueCharacters = true;}
        }
    }
}

if (uniqueCharacters == true) {
    cout << "This string contains all unique characters \n";
}
if (uniqueCharacters == false) {
    cout << "This string does not contain all unique characters \n";
}

- lottie3