[LeetCode] Longest Word in Dictionary through Deleting 删除後得到的字典中的最長單詞

Given a string and a string dictionary, find the longest string in the dictionary that can be formed by deleting some characters of the given string. If there are more than one possible results, return the longest word with the smallest lexicographical order. If there is no possible result, return the empty string.

Example 1:

Example 2:

Note:

All the strings in the input will only contain lower-case letters.

The size of the dictionary won't exceed 1,000.

The length of all the strings in the input won't exceed 1,000.

這道題給了我們一個字元串，和一個字典，讓我們找到字典中最長的一個單詞，這個單詞可以通過給定單詞通過删除某些字元得到。由于隻能删除某些字元，并不能重新排序，是以我們不能通過統計字元出現個數的方法來判斷是否能得到該單詞，而是隻能老老實實的按順序周遊每一個字元。我們可以給字典排序，通過重寫comparator來實作按長度由大到小來排，如果長度相等的就按字母順序來排。然後我們開始周遊每一個單詞，用一個變量i來記錄單詞中的某個字母的位置，我們周遊給定字元串，如果周遊到單詞中的某個字母來，i自增1，如果沒有，就繼續往下周遊。這樣如果最後i和單詞長度相等，說明單詞中的所有字母都按順序出現在了字元串s中，由于字典中的單詞已經按要求排過序了，是以第一個通過驗證的單詞一定是正确答案，我們直接傳回目前單詞即可，參見代碼如下：

解法一：

上面的方法中用到了sort排序，會占用大量時間，如果我們想進一步優化，就可以不用排序。我們周遊字典中的單詞，然後還是跟上面的方法一樣來驗證目前單詞是否能由字元串s通過删除字元來得到，如果能得到，而且單詞長度大于等于結果res的長度，我們再看是否需要更新結果res，有兩種情況是必須要更新結果res的，一個是目前單詞長度大于結果res的長度，另一種是目前單詞長度和res相同，但是字母順序小于結果res，這兩種情況下更新結果res即可，參見代碼如下：

解法二：