CareerCup

Nice Information share

O(n^2) time, O(n) space.

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

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

		bool terminal_;

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

class Trie {
	public:
		void Add(string const &s)
		{
			Node *n = &root_;
			for (char c : s) {
				n = n->AddChild(c);
			}
			n->terminal_ = true;
		}
		Node *Root()
		{
			return &root_;
		}

	private:
		Node root_;
};

int Count(Trie &trie, string const &s, vector<int> &memo, int idx = 0)
{
	if (idx < 0 ||
		idx > s.size())
	{
		return 0;
	}
	if (idx == s.size()) {
		return (idx == 0) ? 0 : 1;
	}

	if (memo.size() < s.size()) {
		memo.resize(s.size(), -1);
	}
	if (memo[idx] != -1) {
		return memo[idx];
	}

	int count = 0;
	Node *n = trie.Root();
	for (int i = idx; i < s.size(); ++i) {
		n = n->Child(s[i]);
		if (!n) {
			break;
		}
		if (n->terminal_) {
			count += Count(trie, s, memo, i + 1);
		}
	}

	memo[idx] = count;
	return memo[idx];
}

int main()
{
	Trie trie;
	trie.Add("dog");
	trie.Add("eat");
	trie.Add("eats");
	trie.Add("scare");
	trie.Add("care");

	vector<int> memo;
	cout << Count(trie, "dogeatscare", memo) << "\n";
}

I'd like to store the dictionary of all combinations of words up to the string input size in a hash table. Hash of the input and count the outputs that match.

What are the pros and cons of using dictionary (hash) vs Trie.

@cool guy
the hash table is more space effective than a trie due to pointers etc. and therefore a hashtable can be cash friendlier if short enough. If you use hashtable in the naive way, you will need to recalculate the hash for the string with every lookup, which is not so nice. If you write your own hashtable and hash function you can avoid this by reusing the hashvalue of k-1 characters to calculate hash of k characters (expanding prefix). With a trie, you know if a prefix is not in the dict as soon as you expand a character c[k], with a hashtable you will have to expand every prefix to the max word size in order to make sure it's not in there. This makes the hash algorithm ineffective for some crafted sample input. The tries memory disadvantage can be improved using a patricia tree - sometimes compacted trie, but it will never be as compact in memory as a hashtable.

There was a question on LeetCode like this, and I tried to beat the fastest c++ implementation which used a hashtable approach. I tried using a trie and even a patricia tree implementation. It turned out, the time to create the trie dominated the advantage of the faster lookups because it was one dictionary per query, so, that's always a good thing to think about, how many queries per dictionary instance. An other thing I noticed there, the data in the testcases were just not advantageous for the trie implementation. Short dictionary (fits into cache) with relatively short words.

I could imagine a combination being good, create a sort of trie on substrings of words of fixed size, say 5 characters, so for short words it's like a single hashtable, long words that share a prefix, would behave like a trie etc... I haven't seen anybody doing that and haven't thought really about it, but it kind of jumped into my mind right now.

edited:
maybe I should have added, a ptrica trie can be more space effective than a hashtable for crafted input, but it's not the case for a regular western language.

#include<bits/stdc++.h>
using namespace std;
int main()
{
}

The dynamic solution

//Recursion + memoization(DP), Time O(n), Space O(n)
public static int wordBreakDP(Set<String> dict, String str) {
	Set<String> memo = new HashSet<String>();	
	return wordBreakUtil(dict, str, "", memo);
}

public static int wordBreakUtil(Set<String> dict, String str, String ouput, Set<String> memo) {		
	int count = 0;
	if (memo.contains(str))
		return count + 1;	
	if(str.length() == 0) {
		System.out.println(ouput);
		return count + 1;
	}
	
	for (int i = 1; i <= str.length(); i++) {
		String prefix = str.substring(0, i);			
		if(dict.contains(prefix)) {
			memo.add(ouput + " " + prefix);
			count += wordBreakUtil(dict, str.substring(i), ouput + " " + prefix, memo);				
		}
	}		
	return count;
}