Last updated on July 18th, 2024 at 02:55 am

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

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”

1. 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 "";
    }
};

2. 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;        
    }
}

3. 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    
};

4. 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 ans