Question

How to check whether a string can be segmented into a sequence of words from a dictionary in C#

Answer 1

using System;
using System.Collections.Generic;

class Program
{
    static bool WordBreak(string s, HashSet<string> dict) {
        int slen = s.Length;
        List<bool> result = new List<bool>(new bool[slen + 1]);
        result[0] = true; // empty string is always segmentable

        for (int i = 1; i <= slen; i++) {
            for (int j = 0; j < i; j++) {
                if (result[j] && dict.Contains(s.Substring(j, i - j))) {
                    result[i] = true;
                    break;
                }
            }
        }

        return result[slen];
    }

    static void Main()
    {
        var dict = new HashSet<string> {
            "future", "depends", "the", "on",
            "your", "dreams", "start", "today"
        };

        string s = "futuredependsonyourdreams";

        if (WordBreak(s, dict))
            Console.WriteLine("The string can be segmented");
        else
            Console.WriteLine("The string cannot be segmented");
    }
}



/*
run:

The string can be segmented

*/

 

70+ SQL courses for beginners and professionals

Answer 2

using System;
using System.Collections.Generic;

class Program
{
    static bool IsInDict(string word, List<string> dict) {
        foreach (var entry in dict) {
            if (entry == word)
                return true;
        }
        return false;
    }

    static void WordBreak(string str, string result, List<string> dict) {
        int strsize = str.Length;
        for (int i = 1; i <= strsize; i++) {
            string subStr = str.Substring(0, i);

            if (IsInDict(subStr, dict)) {
                if (i == strsize) {
                    Console.WriteLine(result + subStr);
                    return;
                }

                WordBreak(str.Substring(i), result + subStr + " ", dict);
            }
        }
    }

    static void Main()
    {
        string str = "butterflyplaybasketballwithbags";
        List<string> dict = new List<string> {
            "butterfly", "basketball", "bagpiper", "and", "play",
            "with", "butter", "fly", "basket", "ball", "bags"
        };

        WordBreak(str, "", dict);
    }
}



/*
run:

butter fly play basket ball with bags
butter fly play basketball with bags
butterfly play basket ball with bags
butterfly play basketball with bags

*/

 

70+ SQL courses for beginners and professionals