Greedy fuzzy matching takes the first place each query character fits, which can miss a better match later in the name. A file finder wants the best possible score instead.
Ignoring case, choose positions p[0] < p[1] < ... < p[m-1] in name with name[p[k]] equal to query[k]. Each chosen position earns 1 point, 2 more if p[k] === p[k - 1] + 1, and 3 more if it is 0 or the character before it is a space, -, _, /, or .. Write bestScore(query, name) that returns the highest total over all choices, or -1 if no choice exists. An empty query scores 0.
Input: query = "ab", name = "xab a_b" Output: 8
Using a and b at the start of a_b gives (1 + 3) + (1 + 3) = 8, better than the greedy ab in xab, which scores 1 + (1 + 2) = 4.
Input: query = "cfg", name = "config.ts" Output: 6
c starts the name (1 + 3), then f and g earn 1 point each. No other placement exists.
0 <= query.length <= 1000 <= name.length <= 1000Run tries your code on the examples. Submit runs every test, including hidden edge cases, and solves the problem when they all pass.
Ctrl + Enter runs, Ctrl + Shift + Enter submits (⌘ on a Mac).
I'm here to help with #718 Best Fuzzy Alignment Score. I give hints, never the solution, so you get to solve it yourself. Ask for a hint, select code to ask about it, or press Ask Tuto why on a failing test.
Your first 3 answers need no account. for free to keep asking.