Go Language LeetCode Question Solution to the Longest Word in the 720 Dictionary

1 Description

720. The longest word in the dictionary - LeetCode ()

Give an array of stringswordsA dictionary of English. returnwordsThe longest word in which the word iswordsStep by adding a letter to other words in the 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:

enter：words = ["w","wo","wor","worl", "world"]
Output："world"
explain： word"world"Can be"w", "wo", "wor", and "worl"Gradually add a letter to form。

Example 2:

enter：words = ["a", "banana", "app", "appl", "ap", "apply", "apple"]
Output："apple"
explain："apply" and "apple" All can be composed of words in the dictionary。but "apple" The dictionary order is smaller than "apply" 

hint:

1 <= <= 1000

1 <= words[i].length <= 30

All input strings words[i] contain only lowercase letters.

Two Analysis

Since the question requires solving the longest word and its prefixes are present in words, a hashmap can be used to save each string, and of course, it can also be used to do it with set. Then iterate through the entire string container. For each string, as long as its length is greater than or equal to max length, it needs to be processed separately:

word length > max length:

• 1. First determine whether the string meets the requirements, that is, whether its prefixes are all in words;
• 2. If the requirements do not meet, ignore it; if the requirements are met, save it.
• 3. Update the information of max length.

word length == max length:

• 1. First determine whether the string meets the requirements, that is, whether its prefixes are all in words;
• 2. If the requirements do not meet, ignore it; if the requirements are met, save it.
• 3. Compare the current two strings of equal length and select the one with a smaller dictionary order to save.

Three Answers

class Solution {
public:
    string longestWord(vector<string>& words) {
        if( () == 0 ){
            return NULL;
        }
		unordered_map<string, int> hashWord;
		for( auto& hw : words ){
			++hashWord[hw];
		}
		int maxLength = 0;
		string word = "";
		for( auto& w : words ){
			if( maxLength < () ){
				bool cntFlag = false;
				string strW = "";
				for( int i = 0; i < (); ++i ){
					strW += w[i];
					if( !( strW ) ){
						cntFlag = true;
						break;
					}
				}
				if( !cntFlag ){
					word = "";
					word = w;
					maxLength = ();
				}
			}else if( maxLength == () ){
				bool cntFlag = false;
				string strW = "";
				for( int i = 0; i < maxLength; ++i ){
					strW += w[i];
					cout << strW << endl;
					if( !( strW ) ){
						cntFlag = true;
						break;
					}
				}
				if( !cntFlag ){
					for( int i = 0; i < maxLength; ++i ){
						if( word[i] < w[i] ){
							break;
						}else if( word[i] > w[i] ){
							word = "";
							word = w;
						}
					}
				}
			}
		}
		return word;
    }
};

Four Summary

This method is stupid, but it is also easier to understand.

The above is the detailed content of the longest word in the 720 dictionary of Go language LeetCode problem solution. For more information about the longest word in the 720 dictionary of Go language, please pay attention to my other related articles!