Word break problem with dynamic programming

Question

This is the original question.

I have implemented it in both ways. If I enter the word "icecream", should I output "ice" "cream" and also "icecream", or just "ice" and "cream"?

Is this a good example of dynamic programming?

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace ConsoleApplication2
{
 public class DynamicProgramming
 {
 public DynamicProgramming()
 { 
 List<string> dictionary = new List<string>{"mobile","samsung","sam","sung","man","mango",
 "icecream","and","go","i","like","ice","cream"};
 var result = ContainsWordRecursive("ilike",dictionary);
 var result2 = ContainsWordDP("icecream", dictionary);
 }
 private List<string> ContainsWordRecursive(string word, List<string> dictionary)
 {
 List<string> res = new List<string>();
 for (int i = 0; i <= word.Length; i++)
 {
 if(dictionary.Contains(word.Substring(0,i)))
 {
 res.Add(word.Substring(0,i));
 var list = ContainsWordRecursive(word.Substring(i, word.Length - i ),dictionary);
 if(list.Count > 0)
 {
 res.AddRange(list);
 }
 }
 }
 return res;
 }
 private List<string> ContainsWordDP(string word, List<string> dictionary)
 {
 List<string> list = new List<string>();
 bool[] wb= new bool[word.Length+1];
 for (int i = 0; i <= word.Length; i++)
 {
 list.Clear();
 if (wb[i] == false && dictionary.Contains(word.Substring(0, i)))
 {
 wb[i] = true;
 list.Add(word.Substring(0, i));
 }
 if (wb[i] == true)
 {
 if (i == word.Length)
 {
 return list;
 }
 for (int j = i + 1; j <= word.Length; j++)
 {
 if (wb[j] == false && dictionary.Contains(word.Substring(i, j - i)))
 {
 wb[j] = true;
 list.Add(word.Substring(i, j - i));
 }
 // If we reached the last character
 if (j == word.Length && wb[j] == true)
 {
 return list ;
 }
 }
 }
 }
 return list;
 }
 }
}

• Vsevolod Goloviznin: I think you are misunderstanding what a dynamic programming is
• Gilad: @VsevolodGoloviznin Please do elaborate.

Answer 1

The first thing an algorithm needs to be is correct, and yours isn't, at least the recursive version (I didn't look at the second one).

For example, ContainsWordRecursive("ihate", dictionary) returns { "i" }, which I don't think is the right result. Instead, your method should somehow indicate that it failed, for example by returning null.