Practice/Microsoft/Leetcode 93. Restore IP Addresses

Leetcode 93. Restore IP Addresses

CodingMust

Problem

You are given a string s containing alphanumeric characters and an integer k representing the number of segments you need to create. Your task is to generate all possible valid email-like format strings by inserting exactly k-1 separators into the string.

The format works as follows:

• Insert exactly k-1 separator characters (dots .) into the string to create k segments
• The first k-1 segments are separated by dots
• If k > 1, place an @ symbol before the last segment instead of a dot
• Each segment must contain at least one character
• Segments must maintain the original character order from the input string

Return all possible valid formatted strings in any order.

Requirements

1. Insert exactly k-1 separators to create k segments
2. Each segment must be non-empty (at least 1 character)
3. The first k-1 segments should be separated by dots (.)
4. If there are 2 or more segments, replace the last dot with an @ symbol
5. Preserve the original order of characters from the input string
6. Return all valid combinations

Constraints

• 1 <= s.length <= 12
• s contains only alphanumeric characters
• 1 <= k <= min(s.length, 4)
• The string is guaranteed to be long enough to create k segments

Examples

Example 1:

` Input: s = "abc123", k = 2 Output: ["a.bc@123", "ab.c@123", "abc@1.23", "abc@12.3"] Explanation: We need to split into 2 segments with an @ separator.

• "a" + "@" + "bc123" → but we also need a dot in the second part → "a.bc@123" Wait, re-reading: k=2 means 2 segments total, so 1 separator. Actually: ["a@bc123", "ab@c123", "abc@123"] would be for k=2 Let me reconsider based on the test case structure. `

Example 2:

Input: s = "user", k = 2 Output: ["u@ser", "us@er", "use@r"] Explanation: Split into 2 segments. Possible splits are at positions 1, 2, and 3.

Example 3:

Input: s = "xyz", k = 3 Output: ["x.y@z"] Explanation: With 3 characters and 3 segments needed, we can only split as x, y, z. Format as "x.y@z" (first two separated by dot, last one after @).