Problem Brief

Longest Dictionary Tokenization

FULLTIMEPHONE SCREEN

See Google online assessment and hiring insights

You are given a text string and a dictionary of token-to-id mappings. Starting from the beginning of text, repeatedly choose the longest dictionary token that matches the current position and output its id. If no dictionary token matches, output the current character itself and advance by one character.

Return the sequence of emitted ids and literal characters.

1Example 1

Input

text = "applepie", dictionary = [["app","B"],["apple","A"],["pie","P"]]

Output

["A","P"]

Explanation

apple is preferred over app because it is the longest match at index 0.

2Example 2

Input

text = "xabcd", dictionary = [["ab","1"],["abc","2"],["bc","3"]]

Output

["x","2","d"]

Explanation

The first character has no match, then abc is the longest token starting at index 1.

Constraints

Limits and guarantees your solution can rely on.

If multiple dictionary entries have the same token, use the first mapping provided. The tokenization is greedy and scans left to right.

Draft autosaves locally

public String[] encodeWithDictionary(String text, String[][] dictionary) {
    // write your code here
}

Input

text

"applepie"

dictionary

[["app","B"],["apple","A"],["pie","P"]]

Output

["A", "P"]