go語言LeetCode題解720詞典中最長的單詞

更新時(shí)間：2022年12月28日 14:38:50 作者：劉09k11

這篇文章主要為大家介紹了go語言LeetCode題解720詞典中最長的單詞，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪

一描述

720. 詞典中最長的單詞 - 力扣（LeetCode） (leetcode-cn.com)

給出一個(gè)字符串?dāng)?shù)組 words 組成的一本英語詞典。返回 words 中最長的一個(gè)單詞，該單詞是由 words 詞典中其他單詞逐步添加一個(gè)字母組成。

若其中有多個(gè)可行的答案，則返回答案中字典序最小的單詞。若無答案，則返回空字符串。

示例 1：

輸入：words = ["w","wo","wor","worl", "world"]
輸出："world"
解釋： 單詞"world"可由"w", "wo", "wor", 和 "worl"逐步添加一個(gè)字母組成。

示例 2：

輸入：words = ["a", "banana", "app", "appl", "ap", "apply", "apple"]
輸出："apple"
解釋："apply" 和 "apple" 都能由詞典中的單詞組成。但是 "apple" 的字典序小于 "apply"

提示：

1 <= words.length <= 1000

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

所有輸入的字符串 words[i] 都只包含小寫字母。

二分析

由于題目要求求解最長單詞且其前綴都存在在words中，由此可以利用一個(gè)hashmap來保存每一個(gè)字串，當(dāng)然也可以采用set來做。然后再遍歷整個(gè)字串容器，對于每個(gè)字串，只要其長度大于或等于max length，那么就需要分別做處理：

word length > max length:

1、先判斷這個(gè)字串是否符合要求，即它的前綴是否都在words里面;
2、如果不符合要求，則忽略；如果符合要求，則保存。
3、更新max length的信息。

word length == max length:

1、先判斷這個(gè)字串是否符合要求，即它的前綴是否都在words里面;
2、如果不符合要求，則忽略；如果符合要求，則保存。
3、比較當(dāng)前兩個(gè)長度相等的字串，選擇字典序小的那個(gè)保存。

三答案

class Solution {
public:
    string longestWord(vector<string>& words) {
        if( words.size() == 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 < w.length() ){
				bool cntFlag = false;
				string strW = "";
				for( int i = 0; i < w.length(); ++i ){
					strW += w[i];
					if( !hashWord.count( strW ) ){
						cntFlag = true;
						break;
					}
				}
				if( !cntFlag ){
					word = "";
					word = w;
					maxLength = w.length();
				}
			}else if( maxLength == w.length() ){
				bool cntFlag = false;
				string strW = "";
				for( int i = 0; i < maxLength; ++i ){
					strW += w[i];
					cout << strW << endl;
					if( !hashWord.count( 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;
    }
};