CODEWITHSUNDEEP
c#arraysstring
huMpty duMpty
huMpty duMpty

Reputation: 14460

How to check whether a word is composed of other strings in an array

I want to check whether a string is built from another two strings within a given string set.

For example, given the following array:

var arr = new string[] { "b", "at", "bat", "ct", "ll", "ball", "ba"};

I want to return only "bat" and "ball".

That's because they can be composed from two other elements in the array like so: 

"bat" = "b" + "at"
"ball" = "ba" + "ll"

I have tried doing it with a foreach loop, but I'm not quite getting it right. Any help will be much appreciated.

I have done something like

foreach(var x in list)
{
    if (dataaccess.IsThreeCharacters(x))
    {
        for (int i = 0; i < arr.Length; i++)
        {
            for (int j = i; j < arr.Length; j++)
            {
                if(x == arr[i] + arr[j])
                {
                    newlist.Add(x);
                }
            }
        }
    }
}

Upvotes: 2

Views: 195

Answers (2)

Bryan Watts
Bryan Watts

Reputation: 45445

This will give you all of the values that can be composed from other values in the sequence:

var values = new HashSet<string>(new[] { "b", "at", "bat", "ct", "ll", "ball", "ba" });

var compositeValues =
    from value in values
    from otherValue in values
    where value != otherValue
    let compositeValue = value + otherValue
    where values.Contains(compositeValue)
    select compositeValue;

Notice the use of HashSet<string>, which gives O(1) lookup performance, as opposed to the O(N) of an array.

Upvotes: 5

Barracoder
Barracoder

Reputation: 3764

This should work although I'm not vouching for efficiency!

static void Main(string[] args)
    {
        var arr = new string[] { "b", "at", "bat", "ct", "ll", "ball", "ba" };

        var composites = from s in arr
                         from lhs in arr
                         from rhs in arr
                         where s == string.Concat(lhs, rhs)
                         select s;

        foreach (var composite in composites)
        {
            Console.WriteLine(composite);                
        }
        Console.ReadLine();

    }

Upvotes: 1

Related Questions