Solve Two String Problems
Company: Meta
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
The interview included two coding questions:
1. **Exactly one edit apart**
Given two strings `s` and `t`, determine whether they are **exactly one edit apart**.
An edit is one of the following operations applied once:
- Insert a single character
- Delete a single character
- Replace a single character
Return `true` if you can transform one string into the other using exactly one edit, and `false` otherwise.
Example cases:
- `s = "ab", t = "acb"` -> `true`
- `s = "cab", t = "ad"` -> `false`
- `s = "1203", t = "1213"` -> `true`
- `s = "abc", t = "abc"` -> `false`
2. **Validate a word abbreviation**
Given a word `word` and a string `abbr`, determine whether `abbr` is a valid abbreviation of `word`.
Rules:
- Letters in `abbr` must match the corresponding letters in `word`.
- A positive integer in `abbr` means skipping that many characters in `word`.
- Numbers cannot contain leading zeros.
- The abbreviation is valid only if it consumes the entire word exactly.
Example cases:
- `word = "internationalization", abbr = "i12iz4n"` -> `true`
- `word = "apple", abbr = "a2e"` -> `false`
- `word = "substitution", abbr = "s10n"` -> `true`
- `word = "word", abbr = "w02d"` -> `false`
Implement efficient solutions for both problems.
Quick Answer: This question evaluates string manipulation, pattern parsing, and algorithmic problem-solving skills, focusing on edit operations, index and boundary handling, and numeric-token parsing for abbreviations.
Part 1: Exactly One Edit Apart
Given two strings `s` and `t`, determine whether they are exactly one edit apart. One edit means performing exactly one of these operations once: insert a single character, delete a single character, or replace a single character. Return `True` only if one string can be transformed into the other using exactly one edit. If they are already equal, or if they need two or more edits, return `False`.
Constraints
- 0 <= len(s), len(t) <= 100000
- Strings may contain any characters.
- An efficient linear-time solution is expected.
Examples
Input: ('ab', 'acb')
Expected Output: True
Explanation: Insert 'c' into 'ab' to get 'acb'.
Input: ('cab', 'ad')
Expected Output: False
Explanation: More than one edit is required.
Hints
- If the string lengths differ by more than 1, they cannot be exactly one edit apart.
- Use two pointers to scan both strings. At the first mismatch, decide whether it represents a replacement or skipping one character in the longer string.
Part 2: Validate a Word Abbreviation
Given a word `word` and an abbreviation `abbr`, determine whether `abbr` is a valid abbreviation of `word`. Letters in `abbr` must match the corresponding letters in `word`. A positive integer in `abbr` means skipping that many characters in `word`. Numbers in the abbreviation cannot have leading zeros, and the abbreviation is valid only if it consumes the entire word exactly.
Constraints
- 0 <= len(word), len(abbr) <= 100000
- `abbr` contains only letters and digits.
- Numbers in `abbr` represent positive skip lengths and cannot contain leading zeros.
Examples
Input: ('internationalization', 'i12iz4n')
Expected Output: True
Explanation: The abbreviation matches the word by skipping the correct number of characters.
Input: ('apple', 'a2e')
Expected Output: False
Explanation: After matching 'a' and skipping 2 characters, the next letter should be 'l', not 'e'.
Hints
- Walk through both strings with two pointers. When you see digits in `abbr`, parse the whole number before moving on.
- A digit '0' cannot start a number in the abbreviation.