Leetcode Longest word in dictionary through deleting problem solution

YASH PAL,

In this Leetcode Longest word in a dictionary through deleting problem solution we have 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.

Leetcode Longest word in dictionary through deleting problem solution

Problem solution in Python.

def findLongestWord(self, S, D):
    D.sort(key = lambda x: (-len(x), x))
    for word in D:
        i = 0
        for c in S:
            if i < len(word) and word[i] == c:
                i += 1
        if i == len(word):
            return word
    return ""

Problem solution in Java.

class Solution {
	public String findLongestWord(String s, List<String> dictionary) {

		String answer = "";
		String temAnwer = "";
		Collections.sort(dictionary);

		for (String vocabulary : dictionary) {
			int pointer = 0;
			int vocabularyLength = vocabulary.length();
			vocabulary.charAt(pointer);

			for (int i = 0; i < s.length(); i++) {

				if (vocabulary.charAt(pointer) == s.charAt(i)) {

					pointer++;

				}

				if (pointer == vocabularyLength) {
					temAnwer = vocabulary;
					break;
				}

			}

			if (temAnwer.length() > answer.length()) {
				answer = temAnwer;
			}

		}

		return answer;
	}
}

Problem solution in C++.

class Solution {
public:
    
    bool isSubsequence(string a, string b) {
        // to check if string b is a subsequence of a
        int ai = 0;
        int bi = 0;
        while(ai < a.length() and bi < b.length()) {
            if(a[ai]==b[bi]) {
                ai++;
                bi++;
            } else {
                ai++;
            }
        }
        if(bi==b.length()) {
            return true;
        } 
        return false;
    }
    
    string findLongestWord(string s, vector<string>& dictionary) {
        string ans = "";
        for(string b: dictionary) {
            if(isSubsequence(s,b)) {
                if(b.size() > ans.size() or (b.size()==ans.size() and b < ans)) {
                    ans = b;
                }
            }
        }
        return ans;
    }
};

Problem solution in C.

#include <string.h>

static int cmp(void *a, void *b) {
	int res = strlen(*(char**)b) - strlen(*(char**)a);
	return res == 0 ? strcmp(*(char**)a, *(char**)b) : res;
}

static int findOneWord(char *s, char *d) {
	for (; *s && *d; s++)
		if (*s ==  *d)
			d++;
	return !*d;
}

char* findLongestWord(char* s, char** d, int dSize) {
	qsort(d, dSize, sizeof(char**), cmp);
	for (; *d; d++)
		if (findOneWord(s, *d))
			return *d;
	return ""; 
}

coding problems solutions Leetcode Problems Solutions