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.