kqg64g
Last Updated: February 25, 2016
·
1.348K
· lukasz-madon
B2bc42f69510d6a1d2c9cde1c2214d24

Write a program to find the longest word made of other words

c#
using System;
using System.Collections.Generic;
using System.Linq;

namespace LongestWordFromWords
{
    internal class Program
    {
        public static string FindLongestWords(IEnumerable<string> listOfWords)
        {
            if (listOfWords == null) throw new ArgumentException("listOfWords");
            var sortedWords = listOfWords.OrderByDescending(word => word.Length);
            var dict = new HashSet<String>(sortedWords);
            return sortedWords.FirstOrDefault(word => isMadeOfWords(word, dict));
        }

        private static bool isMadeOfWords(string word, HashSet<string> dict)
        {
            if (String.IsNullOrEmpty(word)) return false;
            if (word.Length == 1)
            {
                return dict.Contains(word);
            }
            foreach (var pair in generatePairs(word).Where(pair => dict.Contains(pair.Item1)))
            {
                return dict.Contains(pair.Item2) || isMadeOfWords(pair.Item2, dict);
            }
            return false;
        }

        private static IEnumerable<Tuple<string, string>> generatePairs(string word)
        {
            for (int i = 1; i < word.Length; i++)
            {
                yield return Tuple.Create(word.Substring(0, i), word.Substring(i));
            }
        }

        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));
        }
    }
}
Say Thanks
Respond