This is my solution to the problem in the title. The code is pretty straightforward. The one problem is with substring
; it's \$O(n)\$ in .Net and creates garbage. Any other improvements?
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace LongestWordFromWords
{
internal class Program
{
public static string FindLongestWords(string[] listOfWords)
{
if (listOfWords == null) throw new ArgumentException("listOfWords");
var sortedWords = listOfWords.OrderByDescending(word => word.Length).ToList();
var dict = new HashSet<String>(sortedWords);
foreach (var word in sortedWords)
{
if (isMadeOfWords(word, dict))
{
return word;
}
}
return null;
}
private static bool isMadeOfWords(string word, HashSet<string> dict)
{
if (String.IsNullOrEmpty(word)) return false;
if (word.Length == 1)
{
if (dict.Contains(word)) return true;
else return false;
}
foreach (var pair in generatePairs(word))
{
if (dict.Contains(pair.Item1))
{
if (dict.Contains(pair.Item2))
{
return true;
}
else
{
return isMadeOfWords(pair.Item2, dict);
}
}
}
return false;
}
private static List<Tuple<string, string>> generatePairs(string word)
{
var output = new List<Tuple<string, string>>();
for (int i = 1; i < word.Length; i++)
{
output.Add(Tuple.Create(word.Substring(0, i), word.Substring(i)));
}
return output;
}
private static void Main(string[] args)
{
string[] listOfWords = { "ala", "ma", "kota", "aa", "aabbb", "bbb", "cccc", "aabbbmacccc", "aabbbmaxxcccc" };
string longest = FindLongestWords(listOfWords);
Console.WriteLine(longest);
string[] listOfWords2 = { "cat", "cats", "catsdogcats", "catxdogcatsrat", "dog", "dogcatsdog",
"hippopotamuses", "rat", "ratcatdogcat" };
Console.WriteLine(FindLongestWords(listOfWords2));
}
}
}