Question

How to split text without spaces into a list of words using dictionary-based segmentation in C#

Answer 1

using System;
using System.Collections.Generic;

class SegmentTextCSharp
{
    /*
        Helper: check if a substring is in the dictionary.
        Uses a simple array of strings and linear search.
    */
    static bool dict_contains(string candidate, string[] dict)
    {
        foreach (var word in dict) {
            if (candidate == word)
                return true;
        }
        return false;
    }

    /*
        This function performs the segmentation and prints the result.
        It contains your original DP logic exactly as before.
    */
    static void segment_text(string text, string[] dict)
    {
        int n = text.Length;

        /* dp[i] = index j such that text[j:i] is a valid word and dp[j] is valid */
        int[] dp = new int[n + 1];
        bool[] valid = new bool[n + 1];

        valid[0] = true; /* empty prefix is valid */

        for (int i = 1; i <= n; i++)
        {
            valid[i] = false;
            for (int j = 0; j < i; j++)
            {
                /* Check whether dp[j] contains a valid split point;
                   if it does, it means the prefix text[0:j] can be segmented. */
                if (valid[j])
                {
                    /* Create a lightweight substring representing text[j:i]. */
                    int len = i - j;
                    string candidate = text.Substring(j, len);

                    /* Verify whether this substring is a valid dictionary word. */
                    if (dict_contains(candidate, dict))
                    {
                        /* Record that index j is the previous valid split before i.
                           This means text[j:i] is a valid word and dp[j] was valid. */
                        dp[i] = j;
                        valid[i] = true;

                        /* Stop searching for other j values because we already found
                           a valid segmentation ending at i. */
                        break;
                    }
                }
            }
        }

        /* If dp[n] is not valid, segmentation is impossible */
        if (!valid[n])
        {
            Console.WriteLine("No valid segmentation found.");
            return;
        }

        /* Backtrack to recover words */
        List<string> words = new List<string>();
        int idx = n;

        while (idx > 0)
        {
            int j = dp[idx];
            int len = idx - j;

            string w = text.Substring(j, len);
            words.Add(w);

            idx = j;
        }

        /* Reverse the collected words */
        for (int i = 0; i < words.Count / 2; i++)
        {
            string tmp = words[i];
            words[i] = words[words.Count - 1 - i];
            words[words.Count - 1 - i] = tmp;
        }

        /* Print results */
        Console.WriteLine("Segmentation result:");
        foreach (var w in words)
            Console.WriteLine(w);
    }

    static void Main()
    {
        string text = "thisisatestfoo";

        /* Example dictionary */
        string[] dict = {
            "this", "is", "a", "test", "hello", "world", "foo", "bar"
        };

        /* Call the segmentation function */
        segment_text(text, dict);
    }
}


/*
run:

Segmentation result:
this
is
a
test
foo

*/

 

70+ SQL courses for beginners and professionals

Answer 2

using System;
using System.Collections.Generic;

class SegmentTextCSharp
{
    /*
        Helper: check if a substring is in the dictionary.
        Uses a simple array of strings and linear search.
    */
    static bool dict_contains(string candidate, string[] dict)
    {
        foreach (var word in dict) {
            if (candidate == word)
                return true;
        }
        return false;
    }

    /*
        This function performs the segmentation and returns the result.
        It contains your original DP logic exactly as before.
    */
    static List<string> segment_text(string text, string[] dict)
    {
        int n = text.Length;

        /* dp[i] = index j such that text[j:i] is a valid word and dp[j] is valid */
        int[] dp = new int[n + 1];
        bool[] valid = new bool[n + 1];

        valid[0] = true; /* empty prefix is valid */

        for (int i = 1; i <= n; i++)
        {
            valid[i] = false;
            for (int j = 0; j < i; j++)
            {
                /* Check whether dp[j] contains a valid split point;
                   if it does, it means the prefix text[0:j] can be segmented. */
                if (valid[j])
                {
                    /* Create a lightweight substring representing text[j:i]. */
                    int len = i - j;
                    string candidate = text.Substring(j, len);

                    /* Verify whether this substring is a valid dictionary word. */
                    if (dict_contains(candidate, dict))
                    {
                        /* Record that index j is the previous valid split before i.
                           This means text[j:i] is a valid word and dp[j] was valid. */
                        dp[i] = j;
                        valid[i] = true;

                        /* Stop searching for other j values because we already found
                           a valid segmentation ending at i. */
                        break;
                    }
                }
            }
        }

        /* If dp[n] is not valid, segmentation is impossible */
        if (!valid[n]) {
            return new List<string>(); // return empty list
        }

        /* Backtrack to recover words */
        List<string> words = new List<string>();
        int idx = n;

        while (idx > 0) {
            int j = dp[idx];
            int len = idx - j;

            string w = text.Substring(j, len);
            words.Add(w);

            idx = j;
        }

        /* Reverse the collected words */
        for (int i = 0; i < words.Count / 2; i++) {
            string tmp = words[i];
            words[i] = words[words.Count - 1 - i];
            words[words.Count - 1 - i] = tmp;
        }

        /* Return results */
        return words;
    }

    static void Main()
    {
        string text = "thisisatestfoo";

        /* Example dictionary */
        string[] dict = {
            "this", "is", "a", "test", "hello", "world", "foo", "bar"
        };

        /* Call the segmentation function */
        List<string> words = segment_text(text, dict);

        /* Print results */
        Console.WriteLine("Segmentation result:");
        foreach (var w in words)
            Console.WriteLine(w);
    }
}


/*
run:

Segmentation result:
this
is
a
test
foo

*/

 

70+ SQL courses for beginners and professionals