• Example of original title: the longest word in the dictionary
  • C# method: sort traversal
  • Java method: violence method
• summary

Example of original title: the longest word in the dictionary

An English Dictionary composed of a string array words is given.

Find the longest word, which is composed of a letter gradually added to other words in the words dictionary.

If there are multiple feasible answers, the word with the smallest dictionary order in the answer is returned.

If there is no answer, an empty string is returned.

Example 1:

Input:
words = ["w","wo","wor","worl", "world"]
Output:"world"
Explanation: 
word"world"Can be"w", "wo", "wor", and "worl"Add a letter.

Example 2:

Input:
words = ["a", "banana", "app", "appl", "ap", "apply", "apple"]
Output:"apple"
Explanation:
"apply"and"apple"Can be composed of words in a dictionary. however"apple"The dictionary order of is less than"apply". 

Tips:

• All input strings contain only lowercase letters.
• The length range of words array is [11000].
• The length range of words[i] is [1,30].

C# method: sort traversal

Sort first, and define a dictionary dic to store the words fields

1. Traverse words in turn. Add dic based on the length of 1. If the length is not 1, judge whether the dictionary has a value of less than one length. If it exists, add the dictionary
2. Traverse dic in turn to find the longest string

code:

public class Solution {
    public string LongestWord(string[] words) {
        Dictionary<string, int> dic = new Dictionary<string, int>();
            Array.Sort(words);
            for (int i = 0; i < words.Length; i++)
            {
                if (words[i].Length==1)
                {
                    if(!dic.ContainsKey(words[i])){
                        dic.Add(words[i], 1);
                    }  
                    
                }
                else 
                {
                    if (dic.ContainsKey(words[i].Substring(0,words[i].Length-1))&&!dic.ContainsKey(words[i]))
                    {
                        //dic.Remove(words[i].Substring(0, words[i].Length - 1));
                        dic.Add(words[i], words[i].Length);
                    }
                }
            }
            string res = "";
            int len = 0;
            foreach (var item in dic)
            {
                if (item.Value>len)
                {
                    len = item.Value;
                    res = item.Key;
                }
            }
            return res;
    }
}

results of enforcement

adopt
 Execution time: 124 ms，At all C# Defeated 100.00% of users in submission
 Memory consumption: 45.9 MB，At all C# Defeated 43.90% of users in submission

🌻 Java method: violence method

Train of thought analysis For each word, we can check whether all its prefixes exist. We can speed up the search through the Set data structure

• When we find a word that is longer and all its prefixes exist, we will change the answer.
• Or, we can sort the words in advance, so that when we find a qualified word, we can determine that it is the answer.

code:

class Solution {
    public String longestWord(String[] words) {
        Set<String> wordset = new HashSet();
        for (String word: words) wordset.add(word);
        Arrays.sort(words, (a, b) -> a.length() == b.length()
                    ? a.compareTo(b) : b.length() - a.length());
        for (String word: words) {
            boolean good = true;
            for (int k = 1; k < word.length(); ++k) {
                if (!wordset.contains(word.substring(0, k))) {
                    good = false;
                    break;
                }
            }
            if (good) return word;
        }

        return "";
    }
}

results of enforcement

adopt
 Execution time: 13 ms，At all Java  Defeated 66 in submission.41%User
 Memory consumption: 38.3 MB，At all Java Defeated 94 in submission.50%User

Complexity analysis

Time complexity: O( n )
Space complexity: O(1) 

summary

• Today is the ninety first day of punching out the force deduction algorithm!
• This paper uses C# and Java programming languages to solve problems
• Some methods are also written by Likou God, and they are also shared while learning. Thanks again to the algorithm bosses
• That's the end of today's algorithm sharing. See you tomorrow!