CareerCup

Build a trie for the words. Traverse the trie and add words to each list depending on the root of the trie.

rsrs3

for {"an","dan", "c"}, your codes return [[an], [c], [dan]]
but it should be [[c], [an, dan]]

Can anyone provide the answer for below test case?

[c ca can ba ban b bb 12mn 12mnc]

Can anyone provide the correct answer for below test case:

[c ca can ba ban b bb 12mn 12mnc]

I can think of a O(n^2) algorithm where N = number of words
1. sort the list of words in increasing order of words length.
2. Take the first word and remove it from the list and add it to a new list representing a group.
3. start from the first word and search this substring in all the words bigger than this. If a substring match occurs then remove it from the list and add to the group list.
4. go back to step 2 and repeat with next word in the list.
5. When the last word of the list is scanned then return the groups of words created so far

This is not perfect, but is something and works ok

def sublists(list):
     exit = []
     container = []
     for elem in list:
          tmp_list=[]
          for tmp in list:
               if elem in tmp:
                    tmp_list.append(tmp)
          container.append(tmp_list)
     for elem in container:
          add = True
          for other in container:
               if set(elem) < set(other):
                    add = False
          if add:
               exit.append(elem)
     return exit

class TrieNode {
	public:
		TrieNode()
		{
			terminal_ = false;
		}
		~TrieNode()
		{
			for (auto it = children_.begin(); it != children_.end(); ++it) {
				delete it->second;
			}
			children_.clear();
		}
		TrieNode *InsertChild(char c)
		{
			TrieNode *n = GetChild(c);
			if (n == NULL) {
				n = new TrieNode();
				children_[c] = n;
			}
			return n;
		}
		TrieNode *GetChild(char c)
		{
			auto it = children_.find(c);
			return it == children_.end() ? NULL : it->second;
		}

		bool terminal_;

	private:
		unordered_map<char, TrieNode *> children_;
};

class Trie {
	public:
		void Insert(string const &s)
		{
			TrieNode *n = &root_;
			for (char c : s) {
				n = n->InsertChild(c);
			}
			n->terminal_ = true;
		}
		TrieNode *GetRoot()
		{
			return &root_;
		}

	private:
		TrieNode root_;
};

vector<vector<string>> Group(vector<string> const &words)
{
	Trie trie;
	for (auto const &w : words) {
		trie.Insert(w);
	}
	unordered_map<string, vector<int>> groups;
	for (int idx = 0; idx < words.size(); ++idx) {
		string const &w = words[idx];
		for (int i = 0; i < w.size(); ++i) {
			TrieNode *n = trie.GetRoot();
			for (int j = i; j < w.size() && n; ++j) {
				n = n->GetChild(w[j]);
				if (n &&
					n->terminal_)
				{
					int size = j - i + 1;
					if (size < w.size()) {
						groups[w.substr(i, size)].push_back(idx);
					}
				}
			}
		}
	}
	vector<vector<string>> out;
	for (auto const &g : groups) {
		if (!g.second.empty()) {
			vector<string> v;
			v.push_back(g.first);
			for (int i : g.second) {
				v.push_back(words[i]);
			}
			out.push_back(v);
		}
	}
	return out;
}