Backtracking String Combination from Set

gistfile1.txt

/*

Given a string and a set of words, break the string into a list of words from the set. If the string can not be segmented fully, return an empty list.

Example:
Set: {"jump", "jumped", "jumpedov", "over", "some", "thing", "something"}
String: "jumpedoversomething", 
Can return [“jumped”, “over”, “something”] or  [ “jumped”, “over”, “some”, “thing”]


Example:

"any" "cat" "a" "ca" "can" "eat" "n" "anyc" "at"
       
string: "anycatcaneat"

return: "any", "cat", "can", "eat || "any" "cat" "ca" "n" "eat" || "anyc" "at" "can" "eat" || "anyc" "at" "ca" "n" "eat"

Complexity:
O(2^N)
O(2^N)

Edge Case:
aaaaaaaaaaaaaaaaaab
{a aa aaa aaaa... }


         
                    i  
                    j
string: "anycatcaneat"


*/
using System;
using System.Collections.Generic;

class Solution
{
    static void Main(string[] args)
    {

    }
    
    public class PrefixSuffix
    {
        public string Prefix {get;set;}
        public string Suffix {get;set;}
        
        public PrefixSuffix (string p, string s)
        {
            Prefix = p;
            Suffix = s;
        }
    }
    
    public static string FindFullSegment (string input, List<string> words)
    {
        List<List<string>> results = new List<List<string>>();
        
        if (input == null || input.Length < 1 || words == null || words.Count < 1)
        {
            return results;
        }
        
        HashSet<string> wordSet = new HashSet<string>();
        
        foreach (string word in words)
        {
            if (!wordSet.Contains(word))
            {
                wordSet.Add(word);
            }
        }
        
        Helper(input, new PrefixSuffix(String.Empty, input), wordSet, new List<string>(), results);

        return results;

    }
    
    public static void Helper (string input, PrefixSuffix pair, HashSet<string> wordSet, List<string> currentList, List<List<string>> results)
    {
        string pre = pair.Prefix;
        string suff = pair.Suffix;
        
        string potential = pre;
        
        while (potential.Length < input.Length)
        {
            string sub = String.Empty;
            
            for (int i = 0; i < suff.Length; i++)
            {
                sub += suff[i];
                if (wordSet.Contains(sub))
                {      
                    potential += sub;
                    currentList.Add(sub);
                    if (i < suff.Length - 1)
                    {
                        PrefixSuffix newPair = new PrefixSuffix(potential, suff.Substring(i+1));
                        Helper(input, newPair, wordSet, currentList, results);
                    }
                    else
                    {
                        PrefixSuffix newPair = new PrefixSuffix(potential, suff[i].ToString());
                        Helper(input, newPair, wordSet, currentList, results);
                    }
                }
            }
            
            if (potential.Length < input.Length)
            {
                break;
            }
        }
        
        if (potential == input)
        {
            results.Add(currentList);
        }
    }
}