Longest Word In Dictionary Through Deleting Problem


Description

LeetCode Problem 524.

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

Example 1:

1
2
Input: s = "abpcplea", dictionary = ["ale","apple","monkey","plea"]
Output: "apple"

Example 2:

1
2
Input: s = "abpcplea", dictionary = ["a","b","c"]
Output: "a"

Constraints:

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


Sample C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    bool canFormByDeleting(string word, string str) {
        int word_i = 0, str_i = 0;
        while (word_i < word.size() && str_i < str.size()) {
            if (word[word_i] == str[str_i])
                word_i++; 
            str_i++;
        }
        return word_i == word.size();
    }
    
    string findLongestWord(string s, vector<string>& d) {
        string res = "";
        for (auto str : d) {
            if (canFormByDeleting(str, s)) {
                if (str.size() > res.size() || (str.size() == res.size() && str < res))
                    res = str;
            }
        }
        return res;
    }
};




Related Posts

Largest Number At Least Twice Of Others Problem

LeetCode 747. You are given an integer array nums where...

Third Maximum Number Problem

LeetCode 414. Given an integer array nums, return the third...

Queue Reconstruction By Height Problem

LeetCode 406. You are given an array of people, people,...

Minimum Moves To Equal Array Elements II Problem

LeetCode 462. Given an integer array nums of size n,...

Assign Cookies Problem

LeetCode 455. Assume you are an awesome parent and want...