Skip to content

Instantly share code, notes, and snippets.

@tungurlakachakcak
Created March 8, 2024 13:19
Show Gist options
  • Save tungurlakachakcak/11d207eaf1624339cb77cbb36b77d680 to your computer and use it in GitHub Desktop.
Save tungurlakachakcak/11d207eaf1624339cb77cbb36b77d680 to your computer and use it in GitHub Desktop.
Program for finding words that contain a specific character
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <unordered_set>
std::string readLine(std::istream& in) {
std::string str;
std::getline(in, str);
return str;
}
class CharacterFinder {
public:
CharacterFinder(const std::string& str) {
buildLookupTable(str);
}
std::vector<std::string> getWords(const char c) const {
int i = calcIdx(c);
if (i == -1) return {};
return lookupTable[i];
}
private:
// There will be 26 elements in the outer vector - one for each character in the english language.
// We will use lowercase characters as indexes, i.e. a = 0, b = 1, etc.
std::vector<std::vector<std::string>> lookupTable;
void buildLookupTable(const std::string& str) {
const size_t totalLetters = 26;
lookupTable.resize(totalLetters);
std::vector<std::string> words = split(str);
for (const std::string& word : words) {
for (const char c : word) {
int idx = calcIdx(c);
if (idx == -1) continue;
lookupTable[idx].push_back(word);
}
}
}
static int calcIdx(const char c) {
int i = (int)std::tolower(c) - 97;
if (i < 0 || i > 25) { return -1; }
return i;
}
static std::vector<std::string> split(const std::string& str) {
size_t start = 0;
size_t end = 0;
size_t strSize = str.size();
std::vector<std::string> res;
while (end <= strSize) {
const char current = str[end];
if (!std::isalpha(current)) {
// We found a delimiter
if (end - start > 0) {
std::string part = str.substr(start, end - start);
res.push_back(part);
}
end++;
start = end;
}
else {
end++;
}
}
return res;
}
};
static std::vector<std::string> formatWords(const std::vector<std::string>& words) {
std::unordered_set<std::string> dedupWordsSet;
for (const auto& word : words) {
dedupWordsSet.insert(word);
}
std::vector<std::string> dedupWords;
for (const auto& word : dedupWordsSet) {
dedupWords.push_back(word);
}
std::sort(dedupWords.begin(), dedupWords.end());
return dedupWords;
}
static std::string join(const std::vector<std::string>& words, const std::string& delim) {
std::string res;
const size_t lastWordIdx = words.size() - 1;
for (size_t i = 0; i < words.size(); i++) {
res += words[i];
if (i != lastWordIdx) {
res += delim;
}
}
return res;
}
int main()
{
CharacterFinder finder(readLine(std::cin));
char c;
while ((c = getchar()) != '.') {
if (c == '\n') continue;
std::vector<std::string> words = formatWords(finder.getWords(c));
std::string res = words.empty() ? "---" : join(words, " ");
std::cout << res << '\n';
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment