Leetcode -524- Matches the longest word in the dictionary by removing letters

[Blog link]

The path to learning at 🐔

The nuggets home page

[答 案]

Topic link

[making address]

Making the address

[B].

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

Tip:

• 1 <= s.length <= 1000
• 1 <= dictionary.length <= 1000
• 1 <= dictionary[i].length <= 1000
• S and dictionary[I] consist only of lowercase English letters

Related Topics

• An array of
• Double pointer
• string
• The sorting
• 👍 👎 0 204

Idea 1: Violent scanning

• The simplest global scan, and then according to the conditions to do filtering
• A double pointer determines whether a dictionary word is satisfied

public String findLongestWord(String s, List<String> dictionary) {
            String res = "";
            int n = s.length();
            for (String tar : dictionary) {
                int l = 0, r = 0;
                while (l < n && r < tar.length()) {
                    if (s.charAt(l) == tar.charAt(r)) {
                        l++;
                        r++;
                    } else{ l++; }}if (r == tar.length()) {
                    if (res.length() < tar.length()) {
                        res = tar;
                    } else if(res.length() == tar.length()) { res = compare(tar, res) ? tar : res; }}}return res;
        }

        boolean compare(String s1, String s2) {
            for (int i = 0; i < s1.length() && i < s2.length(); i++) {
                if(s1.charAt(i) ! = s2.charAt(i)) {returns1.charAt(i) < s2.charAt(i); }}return s1.length() < s2.length();
        }
Copy the code

• Time complexity O(n∗mn* MN ∗m) M indicates the maximum length of strings, and n indicates the number of strings
• Time complexity O(111) Space excluding the declaration string does not require additional space processing

Idea 2: sort + double pointer

• You can define the sorting algorithm, sort it, find the first one

public String findLongestWord(String s, List<String> dictionary) {
    int n = s.length();
    Collections.sort(dictionary, new Comparator<String>() {
        @Override
        public int compare(String o1, String o2) {
            if(o1.length() ! = o2.length()) {return o2.length() - o1.length();
            }
            for (int i = 0; i < o1.length(); i++) {
                if(o1.charAt(i) ! = o2.charAt(i)) {returno1.charAt(i) - o2.charAt(i); }}return 0; }});for (String tar : dictionary) {
        int l = 0, r = 0;
        while (l < n && r < tar.length()) {
            if (s.charAt(l) == tar.charAt(r)) {
                l++;
                r++;
            } else{ l++; }}if (r == tar.length()) {
            returntar; }}return "";
}
Copy the code

• Time complexity O(m∗ LGM +m∗nm* LGM + M *nm∗ LGM +m∗n) M represents the maximum length of strings, n represents the number of strings, and the time complexity of sorting NLGN
• Time complexity O(111) Space excluding the declaration string does not require additional space processing