FastPrepMaximum-Value Word Derivation Path

Maximum-Value Word Derivation Path

Duolingo logoDuolingo● MediumINTERNPHONE SCREEN
Learn

Problem statement

A direct derivation rearranges all letters of one word and adds exactly one letter. Existing letters cannot be removed or replaced, and repeated letters count separately.

Each vocabulary[i] has integer value values[i]. Given start and target, return a derivation path from start to target whose total word value is largest.

For this exercise, assume vocabulary labels are unique, both endpoints are listed, and every intermediate word must also be listed. The total includes every word in the path, including start and target.

For this exercise, assume equal totals choose the lexicographically smallest complete word list: compare the first differing word using ordinary lowercase lexicographic order. Return an empty array if target is unreachable. When start equals target, return the one-word zero-step path.

Function

bestDerivationPath(start: String, target: String, vocabulary: String[], values: int[]) → String[]

Examples

Example 1

start = "a"target = "abc"vocabulary = ["a","ab","ac","abc"]values = [1,3,8,2]return = ["a","ac","abc"]

This authored example chooses a, ac, abc with total 11 instead of the total 6 through ab.

Example 2

start = "ab"target = "abcd"vocabulary = ["ab","abc","acb","abcd"]values = [2,5,5,3]return = ["ab","abc","abcd"]

This authored tie selects ab, abc, abcd before ab, acb, abcd in lexicographic path order.

Example 3

start = "two"target = "woutx"vocabulary = ["two","woutx"]values = [4,9]return = []

This authored wrapper preserves the reported starting word but has no listed length-four intermediate; no path exists.

Constraints

  • For this exercise, assume 1 <= vocabulary.length <= 25 and values.length == vocabulary.length.
  • Every vocabulary word is a unique nonempty lowercase English string of length at most 12. Start and target occur in vocabulary.
  • For this exercise, assume -1000 <= values[i] <= 1000.

More Duolingo problems

See Duolingo hiring insights
public String[] bestDerivationPath(String start, String target, String[] vocabulary, int[] values) {
    // Write your code here.
    return new String[0];
}
start"a"
target"abc"
vocabulary["a","ab","ac","abc"]
values[1,3,8,2]
expected["a", "ac", "abc"]
Checking account…