5
\$\begingroup\$

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;
        }
    }
}
\$\endgroup\$
  • \$\begingroup\$ I think you are misunderstanding what a dynamic programming is \$\endgroup\$ – Vsevolod Goloviznin Dec 14 '14 at 21:45
  • 2
    \$\begingroup\$ @VsevolodGoloviznin Please do elaborate. \$\endgroup\$ – Gilad Dec 14 '14 at 21:57
1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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