Longest Word in Dictionary through Deleting LeetCode Solution

Here, We see Longest Word in Dictionary through Deleting LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.

List of all LeetCode Solution

Longest Word in Dictionary through Deleting LeetCode Solution

Longest Word in Dictionary through Deleting LeetCode Solution

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”

Longest Word in Dictionary through Deleting Solution 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 "";
    }
};Code language: PHP (php)

Longest Word in Dictionary through Deleting Solution 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;        
    }
}Code language: JavaScript (javascript)

Longest Word in Dictionary through Deleting Solution 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    
};Code language: JavaScript (javascript)

Longest Word in Dictionary through Deleting Solution 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 ansCode language: HTML, XML (xml)
Scroll to Top