This is the question of the Day for 2021-9-14 in LeetCode: “524. Match the longest word in the dictionary by deleting letters”

1. Topic description

Given a string S and an array of strings called dictionary as a dictionary, find and return the longest string in the dictionary, which can be obtained by removing some characters from S.

If there is more than one answer, return the string with the longest length and smallest lexicographic order. If the answer does not exist, an empty string is returned.

Example 1:

Input: s = "abpcplea", dictionary = ["ale","apple","monkey","plea"] output: "apple"Copy the code

Example 2:

Input: s = "abpcplea", dictionary = [" a ", "b", "c"] output: "a"Copy the code

2. Answer

  1. Sort dictionaries in descending order by string length, dictionary order first
  2. Check each string in the dictionary to see if it meets the criteria
  3. Double-pointer traversal is used to judge when testing
const findLongestWord = (s, dictionary) = > {
    // Sort by string length in descending and lexicographical order
    dictionary.sort((a, b) = > (a.length === b.length ? a.localeCompare(b) : b.length - a.length));
    const lenS = s.length;

    for (const word of dictionary) {
        // Two Pointers
        let [S, W] = [0.0];
        const lenW = word.length;
        while (S < lenS && W < lenW) {
            if (s[S] === word[W]) W++;
            S++;
        }
        // If the W pointer ends, word matching is complete
        if (W === lenW) return word;
    }
    return ' ';
};
Copy the code

😄 has recently created an open source repository to summarize LeetCode’s daily problems. It is currently available in C++ and JavaScript, and you are welcome to provide other language versions!

🖥️ Warehouse address: “One of the Day series”