Write a program that breaks up a string of words with no spaces into a string with the appropriate spaces

GoogleInterview-WordsSeparation1.cpp

// This solution use another char array (which mean space complexity of O(n) where n in the length of the string)

#include <string>
#include <set>
#include <iostream>

using namespace std;

class Dictionary {

public:
	static void add(string word) {
		words.insert(word);
	}

	static bool contains(string& str) {
		return (words.find(str) != words.end());
	}

private:
	static set<string> words;
};

// Assumptions: enough space int dst
void add_spaces(char* src, char* dst) {
	if (src == nullptr || dst == nullptr)
		return;

	int length = strlen(src);
	if (length == 0) {
		dst[0] = '\0';
		return;
	}

	int start = 0;
	int i = 0;
	int j = 0;
	for (i=0, j=0 ; i <= length ; i++,j++) {
		string word = string(&src[start],i-start);
		
		if (Dictionary::contains(word)) {
			dst[j] = ' ';
			j++;
			start = i;
		}

		dst[j]=src[i];
	}

	dst[j] = '\0';
}

void test(char* str) {
	printf("Before: %s, ", str);
	char* dst = new char[strlen(str) * 2 * sizeof(char)];
	add_spaces(str, dst);
	printf("After: %s\n", dst);
	delete dst;
}

set<string> Dictionary::words; // compilation fix

int main() {
	Dictionary::add("I");
	Dictionary::add("want");
	Dictionary::add("that");
	Dictionary::add("job");

	test("Iwantthatjob");
	test("Iwantjob");
}

GoogleInterview-WordsSeparation2.cpp

// This solution use another string (which mean space complexity of O(n) where n in the length of the string)

#include <string>
#include <set>
#include <iostream>

using namespace std;

class Dictionary {

public:
	static void add(string word) {
		words.insert(word);
	}

	static bool contains(string& str) {
		return (words.find(str) != words.end());
	}

private:
	static set<string> words;
};

void add_spaces(string& src, string& dst) {
	if (src.empty()) {
		dst = "";
		return;
	}
	
	int length = src.length();

	int start = 0;
	int i = 0;

	for (i=0 ; i <= length ; i++) {
		string word = string(&src[start],i-start);

		if (Dictionary::contains(word)) {
			dst += ' ';
			start = i;
		}

		dst += src[i];
	}
}

void test(string src) {
	cout << "Before: " << src << ",";
	string dst;
	add_spaces(src, dst);
	cout << "After: " << dst << endl;
}

set<string> Dictionary::words; // compilation fix

int main() {
	Dictionary::add("I");
	Dictionary::add("want");
	Dictionary::add("that");
	Dictionary::add("job");

	test("Iwantthatjob");
	test("Iwantjob");
}

GoogleInterview-WordsSeparation3.cpp

// This solution use the same string (which mean space complexity of O(1). Runtime complexity is now slower because of insert operation - O(n^2))

#include <string>
#include <set>
#include <iostream>

using namespace std;

class Dictionary {

public:
	static void add(string word) {
		words.insert(word);
	}

	static bool contains(string& str) {
		return (words.find(str) != words.end());
	}

private:
	static set<string> words;
};

void add_spaces(string& src) {
	if (src.empty()) {
		return;
	}
	
	int start = 0;
	int i = 0;

	for (i=0 ; i <= src.length() ; i++) {
		string word = src.substr(start,i-start);

		if (Dictionary::contains(word)) {
			src.insert(start," ");
			i++;
			start = i;
		}
	}
}

void test(string src) {
	cout << "Before: " << src << ", ";
	add_spaces(src);
	cout << "After: " << src << endl;
}

set<string> Dictionary::words; // compilation fix

int main() {
	Dictionary::add("I");
	Dictionary::add("want");
	Dictionary::add("that");
	Dictionary::add("job");

	test("Iwantthatjob");
	test("Iwantjob");
}