Skip to content

Instantly share code, notes, and snippets.

@animatedlew
Last active February 21, 2017 01:53
Show Gist options
  • Select an option

  • Save animatedlew/bb87999f40be262238849d492d14485e to your computer and use it in GitHub Desktop.

Select an option

Save animatedlew/bb87999f40be262238849d492d14485e to your computer and use it in GitHub Desktop.
Implement an algorithm to determine if a string has all unique characters. What if you cannot use additional data structures?
/*
* Implement an algorithm to determine if a string has all unique
* characters. What if you cannot use additional data structures?
*/
#define CATCH_CONFIG_MAIN
#include "catch.hpp"
#include <iostream>
using namespace std;
bool find(const char& c, const string& str) {
for (auto &s:str) if (s == c) return true;
return false;
}
bool isUnique(string const& str) {
bool hasMatch = false;
for (auto i = 0; i < str.size(); i++)
hasMatch = hasMatch || find(str[i], str.substr(i + 1));
return !hasMatch;
}
TEST_CASE( "Determine if string has unique characters", "[isUnique]" ) {
REQUIRE(isUnique("better") == false);
REQUIRE(isUnique("mountain") == false);
REQUIRE(isUnique("unique") == false);
REQUIRE(isUnique("news") == true);
REQUIRE(isUnique("house") == true);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment