0

I'm learning C# by reading a books and other online tutorials (homeandlearn.co.uk)

I've managed to do the FizzBuzz excercise but struggling with the below excercise. Any help would be much much appreciated.

Please explain in detail so i can learn aswell.

Excercise

filter a list of strings that should pass only six letter strings that are composed of two concatenated smaller strings that are also in the list.

For example, given the list

acks, top, cat, gr, by, bar,lap, st, ely, ades

The list should return

stacks, laptop, grades, barely

Because these are a concatenation of two other strings:

st + acks = stacks

lap + top = laptop

gr + ades = grades

bar + ely = barely

Improve this question
5
  • 3
    Filter is a poor word choice, construct would be better. Commented Oct 5, 2011 at 14:09
  • 1
    unless the example is wrong and stacks is meant to be in the list as well Commented Oct 5, 2011 at 14:12
  • 5
    what about cat+top = catop, gracks, byacks, etc? The excercise is poorly written. Commented Oct 5, 2011 at 14:12
  • You're missing another list: a set of dictionary words limiting potential results Commented Oct 5, 2011 at 14:16
  • I hope young english boys (and girls) aren't teached the english of the Excercise :-) Commented Oct 5, 2011 at 14:32

5 Answers 5

Reset to default
1

In LINQ:

// The strings (it's equivalent to new string[])
var strs = new[] { "acks", "top", "cat", "gr", "by", "bar", "lap", "st", "ely", "ades" };

// We group the strings by length.
var strsByLength = strs.ToLookup(p => p.Length);

// For each string we match the string with all the strings with the "right" length (6 - current string length) and we sum them (p, q) => p + q.
var result = strs.SelectMany(p => strsByLength[6 - p.Length], (p, q) => p + q);

I'm using the ToLookup to make this problem "medium" complexity a little less than O(n^2). Clearly if all the strings are long 3, the problem is still O(n^2).

I'm usign the SelectMany that, alone, is a little advanced LINQ.

I'll add, if you have a dictionary of "good" words, a solution could be this. It's using the dictionary as a black box: you can check if a word is IN the dictionary (technically an HashSet) but you can't directly use the dictionary to help you finding the words.

// The list of good words
var words = new[] { "stacks", "laptop", "grades", "barely" };

// Made in an `HashSet` to make it O(1) to check for them.
var wordsSet = new HashSet<string>(words);

// Here we create a temporary object (p, q) => new { p, q, sum = p + q } containing the two "parts" of the word and the complete word and then we filter the result for only the words contained in the wordsSet.
var result2 = strs.SelectMany(p => strsByLength[6 - p.Length], (p, q) => new { p, q, sum = p + q }).Where(p => wordsSet.Contains(p.sum));
Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

0

There really are a lot of ways to do this. Here's one that uses pairing:

        //grab all possible pairings in one data structure
        List<KeyValuePair<string, string>> pairs = new List<KeyValuePair<string, string>>();
        string[] list = { "acks", "top", "cat", "gr", "by", "bar", "lap", "st", "ely", "ades" };
        foreach (string first in list)
        {
            foreach (string second in list)
            {
                pairs.Add(new KeyValuePair<string, string>(first, second));
            }
        }

        //test each pairing for length and whatever else you want really
        List<string> sixLetterWords = new List<string>();
        foreach (KeyValuePair<string, string> pair in pairs)
        {
            string testWord = pair.Key + pair.Value;
            if (testWord.Length == 6)
            {
                sixLetterWords.Add(testWord);
            }
        }
Improve this answer

Comments

0

Divide and conquer. First, you need to find a way to get all possible pairs of strings (like first and second, first and third, ..., second and third, etc.). Next, for each pair you check whether the list in question contains either s1 + s2 or s2 + s1.

Improve this answer

3 Comments

Thank you for the help, as you know i'm learning and quite basic in C#, could you please slightly elaborate or even if you can write quick code so i can learn and follow. thanks
It's only worth creating pairs whose joint length is 6.
@Mo. - It would serve no purpose for us to give you example. What Anton suggested is a trivial programming skill, you need to do this on your own, otherwise you learn nothing.
0

The easiest way would be to do a nested for loop, and try every combination and test to see if it's 6 in length. Something like:

For <each string> AS a
    For <every string> AS b
        If (a+b).length = 6 then
            // we have a match!

I'll leave it to you to translate this into actual code

Improve this answer

Comments

0

You already know how to concatenate two strings. You also know how to check the length of the string.

So, create a new list from the items in the first list and exclude items with length != 6.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.