524. Longest Word in Dictionary through Deleting #

Problem #

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

Example 1:

Input:
s = "abpcplea", d = ["ale","apple","monkey","plea"]

Output: 
"apple"

Example 2:

Input:
s = "abpcplea", d = ["a","b","c"]

Output: 
"a"

Note:

• All the strings in the input will only contain lower-case letters.
• The size of the dictionary won’t exceed 1,000.
• The length of all the strings in the input won’t exceed 1,000.

Problem Summary #

Given an initial string and a string array, find the longest string in the string array that can be obtained by deleting characters from the initial string. If there are multiple solutions for the longest string, output the solution with the smallest lexicographical order.

Solution Approach #

For this problem, simply use an O(n^2) brute-force loop. Pay attention to the requirements for the final answer: if the strings are all the longest, output the one with the smallest lexicographical order. You can just use string comparison to obtain the lexicographically smallest string.

Code #

package leetcode

func findLongestWord(s string, d []string) string {
	res := ""
	for i := 0; i < len(d); i++ {
		pointS := 0
		pointD := 0
		for pointS < len(s) && pointD < len(d[i]) {
			if s[pointS] == d[i][pointD] {
				pointD++
			}
			pointS++
		}
		if pointD == len(d[i]) && (len(res) < len(d[i]) || (len(res) == len(d[i]) && res > d[i])) {
			res = d[i]
		}
	}
	return res
}