2021-01-22
https://leetcode.com/problems/longest-word-in-dictionary-through-deleting/

Description:

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:
Input:
s = "abpcplea", d = ["ale","apple","monkey","plea"]
Output:
"apple"

Example 2:
Input:
s = "abpcplea", d = ["a","b","c"]
Output:
"a"

解題思路：

1. 判斷一個(gè)字符串是否為另一個(gè)字符串的子字符串。- 雙指針移動(dòng)
2. 依次遍歷列表里的字符串，對(duì)他們進(jìn)行以下操作：
   a. 查看它的長(zhǎng)度是否大于當(dāng)前“最大長(zhǎng)度字符串”（先設(shè)為空），或在長(zhǎng)度相等情況下，是否在字典中排在前。 - 如果不符合上述條件，則無(wú)需查看是否為子字符；
   b. 如果符合，用方程1查看是否為已知字符串的子字符，如果是，則更新當(dāng)前最大字符串的值。
   c. 當(dāng)遍歷完全部字符串，返回當(dāng)前最大字符串。

代碼：

class Solution {
    public String findLongestWord(String s, List<String> d) {
        
        String longestWord = "";
        
        for (String listString : d) {
            int l1 = longestWord.length(), l2 = listString.length();
            if (l1>l2 || (l1==l2 && longestWord.compareTo(listString) < 0)) {
                continue;
            }
            
            if(isSubString(s,listString)) {
                longestWord = listString;
            }
        }
        
        return longestWord;           
    }
    
    private boolean isSubString(String s, String listString) {
        int i=0,j=0;
        while (i<s.length() && j<listString.length()) {
            
            if (s.charAt(i) == listString.charAt(j)) {
                j++;
            }
            i++;
        }
        
        if (j == listString.length()) {
            return true;
        } else {
            return false;
        }
    }
}