String Normalization Combinatorics | Dataford Interview Questions

Grammarly Editor may represent uncertain text with alternatives such as {grammarly|Grammarly}. Given a pattern, generate every possible combination and return the unique results after text normalization.

A pattern contains ordinary text and zero or more non-nested alternative groups. Each group has the form {option1|option2|...}. Alternatives may contain letters, digits, punctuation, and whitespace, but not {, }, or |.

Normalize each generated string by converting it to lowercase, replacing every consecutive whitespace sequence with one space, and removing leading or trailing spaces. Return the normalized strings in lexicographic order, without duplicates.

Formal Specification

Implement generate_normalized_variants(pattern). The input is a string, and the output is a list of strings. Every output string must result from selecting exactly one option from each alternative group, then applying the normalization rules.

Constraints

1 <= len(pattern) <= 1000
The pattern contains at most 12 alternative groups
Every group contains at least two non-empty options
The total number of combinations is at most 5000
Groups are non-nested and braces are balanced

Function Signature

def generate_normalized_variants(pattern):

Your question is String Normalization Combinatorics. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem

Formal Specification

Constraints

1 <= len(pattern) <= 1000
The pattern contains at most 12 alternative groups
Every group contains at least two non-empty options
The total number of combinations is at most 5000
Groups are non-nested and braces are balanced

Function Signature

def generate_normalized_variants(pattern):

Your question is String Normalization Combinatorics. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.