Leetcode July: Word Break II

vector<string> wordBreak(string s, vector<string>& wordDict) {
   unordered_set<string> dict(wordDict.begin(), wordDict.end());
   // memoization table stores all valid word break solutions beginning at index key.
   unordered_map<int, vector<string>> validStringsAtIndex;
   return dp(s, 0, dict, validStringsAtIndex);
}

vector<string> dp(string s, int index, const unordered_set<string>& dict, unordered_map<int, vector<string>>& validStringsAtIndex) 
{
   // prevent repeated recursion over completed index substrings by checking memoization table.
   if(validStringsAtIndex.count(index)) {
	  return validStringsAtIndex[index];
   }
   // iterate over all substrings beginning with current index,
   for(int i=index;i<s.length();i++) {
	  // from length 1 to max length--s.length-index+1
	  string currentSubString = s.substr(index, i-index+1);
	  
	  // if the current substring is a valid word,
	  if(dict.count(currentSubString)) {
		 // and substring is end of string, push back substring as a valid word for index.
		 if(i == s.length()-1) {
			validStringsAtIndex[index].push_back(currentSubString);
		 }
		 // temp vector will contain solutions for all subsequent indices.
		 vector<string> temp = dp(s, i + 1, dict, validStringsAtIndex);
		 // cross current valid substring with all subsequent string solutions.
		 for(auto str : temp) {
			validStringsAtIndex[index].push_back(currentSubString + " " + str);
		 }
	  }
   }
   return validStringsAtIndex[index];
}