Last updated on February 2nd, 2025 at 04:43 am
Here, we see Longest word in Dictionary through Deleting LeetCode Solution. This Leetcode problem is solved in many programming languages, such as C++, Java, JavaScript, Python, etc., with different approaches.
List of all LeetCode Solution
Topics
Sort, Two Pointers
Companies
Level of Question
Medium
Longest Word in Dictionary through Deleting LeetCode Solution
Table of Contents
1. Problem Statement
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:
Input: s = “abpcplea”, dictionary = [“ale”,”apple”,”monkey”,”plea”]
Output: “apple”
Example 2:
Input: s = “abpcplea”, dictionary = [“a”,”b”,”c”]
Output: “a”
2. Coding Pattern Used in Solution
The coding pattern used in this code is “Greedy Algorithm with Subsequence Matching”. The algorithm greedily selects the longest valid word from the dictionary that can be formed as a subsequence of the given string s.
3. Code Implementation in Different Languages
3.1 Longest Word in Dictionary through Deleting C++
class Solution {
public:
string findLongestWord(string s, vector<string>& dictionary) {
sort(begin(dictionary), end(dictionary), [](string a, string b){return a.size() == b.size() && a < b || b.size() < a.size();});
for (int i = 0, lmt = dictionary.size(), j, currLen; i < lmt; i++) {
j = 0, currLen = dictionary[i].size();
for (char c: s) {
if (c == dictionary[i][j]) {
j++;
if (j == currLen) return dictionary[i];
}
}
}
return "";
}
};
3.2 Longest Word in Dictionary through Deleting Java
class Solution {
public String findLongestWord(String s, List<String> dictionary) {
String ans = "";
for (String word : dictionary) {
int a = word.length(), b = ans.length();
if (a < b || (a == b && word.compareTo(ans) > 0)) continue;
int pos = -1;
for (int i = 0; i < a; i++) {
pos = s.indexOf(word.charAt(i), pos + 1);
if (pos == -1) break;
}
if (pos != -1) ans = word;
}
return ans;
}
}
3.3 Longest Word in Dictionary through Deleting JavaScript
var findLongestWord = function(s, dictionary) {
let ans = ""
for (let word of dictionary) {
let a = word.length, b = ans.length
if (a < b || (a === b && word > ans)) continue
let pos = -1
for (let char of word) {
pos = s.indexOf(char, pos + 1)
if (pos === -1) break
}
if (pos !== -1) ans = word
}
return ans
};
3.4 Longest Word in Dictionary through Deleting Python
class Solution(object):
def findLongestWord(self, s, dictionary):
ans = ""
for word in dictionary:
a, b = len(word), len(ans)
if a < b or (a == b and word > ans): continue
pos = -1
for char in word:
pos = s.find(char, pos + 1)
if pos == -1: break
else: ans = word
return ans
4. Time and Space Complexity
| Time Complexity | Space Complexity | |
| C++ | O(d * (s + log d)) | O(1) |
| Java | O(d * s) | O(1) |
| JavaScript | O(d * s) | O(1) |
| Python | O(d * s) | O(1) |
Where:
– d is the size of the dictionary.
– s is the length of the string s.
- The code uses a Greedy Algorithm with Subsequence Matching pattern to solve the problem.
- It iterates through the dictionary, checking if each word can be formed as a subsequence of
s. - The time complexity is O(d * s) for Java, JavaScript, and Python, and O(d * (s + log d)) for C++ due to sorting.
- The space complexity is O(1) since no additional data structures are used.