双指针 [m] #524. Longest Word in Dictionary through Deleting

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. 判断一个字符串是否为另一个字符串的子字符串。- 双指针移动
2. 依次遍历列表里的字符串，对他们进行以下操作：
   a. 查看它的长度是否大于当前“最大长度字符串”（先设为空），或在长度相等情况下，是否在字典中排在前。 - 如果不符合上述条件，则无需查看是否为子字符；
   b. 如果符合，用方程1查看是否为已知字符串的子字符，如果是，则更新当前最大字符串的值。
   c. 当遍历完全部字符串，返回当前最大字符串。

代码：

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;
        }
    }
}