Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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;
        }
    }
}
share|improve this question
    
I think you are misunderstanding what a dynamic programming is – Vsevolod Goloviznin Dec 14 '14 at 21:45
2  
@VsevolodGoloviznin Please do elaborate. – Gilad Dec 14 '14 at 21:57
up vote 1 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.