Ambiguous Coordinates

Med

#0770Time: O(N^4), where N is the length of the digit string. The main loop runs N-1 times. Inside, generating possibilities for a substring of length k takes O(k^2). Combining results from two lists of size O(i) and O(N-i) takes O(i * (N-i) * N) time. The total time is dominated by this combination step, summing to O(N^4).Space: O(N^4), where N is the length of the digit string. The output list can contain O(N^3) coordinate strings, each of length O(N).

Patterns

Backtracking Enumeration

Data structures

String

Prompt

We had some 2-dimensional coordinates, like "(1, 3)" or "(2, 0.5)". Then, we removed all commas, decimal points, and spaces and ended up with the string s.

For example, "(1, 3)" becomes s = "(13)" and "(2, 0.5)" becomes s = "(205)".

Return a list of strings representing all possibilities for what our original coordinates could have been.

Our original representation never had extraneous zeroes, so we never started with numbers like "00", "0.0", "0.00", "1.0", "001", "00.01", or any other number that can be represented with fewer digits. Also, a decimal point within a number never occurs without at least one digit occurring before it, so we never started with numbers like ".1".

The final answer list can be returned in any order. All coordinates in the final answer have exactly one space between them (occurring after the comma.)

Example 1:

Input: s = "(123)"
Output: ["(1, 2.3)","(1, 23)","(1.2, 3)","(12, 3)"]

Example 2:

Input: s = "(0123)"
Output: ["(0, 1.23)","(0, 12.3)","(0, 123)","(0.1, 2.3)","(0.1, 23)","(0.12, 3)"]
Explanation: 0.0, 00, 0001 or 00.01 are not allowed.

Example 3:

Input: s = "(00011)"
Output: ["(0, 0.011)","(0.001, 1)"]

Constraints:

4 <= s.length <= 12
s[0] == '(' and s[s.length - 1] == ')'.
The rest of s are digits.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach systematically explores all possibilities. The core idea is to split the input digit string into two parts, x_str and y_str, which will form the x and y coordinates. For each split, we generate all valid numerical interpretations for x_str and y_str. A number can be an integer or a decimal, subject to certain rules about leading and trailing zeros. Finally, we combine every valid x-interpretation with every valid y-interpretation to form the final coordinate pairs.

Algorithm

Extract the digit string digits from the input s by removing the parentheses. Let its length be n.
Create a list result to store the final coordinate strings.
Loop with an index i from 1 to n-1. This i represents the split point.
In each iteration, split digits into two substrings: s1 = digits.substring(0, i) and s2 = digits.substring(i).
Call a helper function generateValidNumbers(str) for both s1 and s2 to get lists of their valid number representations, list1 and list2.
The generateValidNumbers(str) function works as follows:
- It checks if str itself is a valid integer (no leading zeros unless it's just "0"). If so, add str to its results.
- It then iterates through all possible decimal point positions in str. For each split into an integer part int_part and a fractional part frac_part:
  - It checks if int_part is a valid integer part (no leading zeros unless it's "0").
  - It checks if frac_part is a valid fractional part (no trailing zeros).
  - If both are valid, it combines them as "int_part.frac_part" and adds to its results.
- It returns the list of valid representations.
After getting list1 and list2, iterate through all pairs (x, y) where x is in list1 and y is in list2.
For each pair, format it as "(x, y)" and add it to the result list.
Return result.

Walkthrough

First, we remove the outer parentheses from the input string s to get a string of digits. We then iterate through all possible split points of this digit string. A split divides the string into two non-empty substrings, s1 and s2. For each substring (s1 and s2), we find all the ways it can be interpreted as a valid number. This is done by a helper function, generateValidNumbers. The generateValidNumbers function considers two cases for a given digit string t:

Integer: t is a valid integer if it's "0" or doesn't start with '0'.
Decimal: t can be split into an integer part i and a fractional part f. This is a valid decimal if i is a valid integer and f does not end with '0'. The function tries all possible positions for the decimal point. The helper function returns a list of all valid string representations for s1 and s2. We then take the Cartesian product of these two lists. Each pair (x, y) is formatted into the string "(x, y)" and added to our final answer list. The code snippet below illustrates this logic.

1class Solution {2    public List<String> ambiguousCoordinates(String s) {3        List<String> result = new ArrayList<>();4        String digits = s.substring(1, s.length() - 1);5        int n = digits.length();6 7        for (int i = 1; i < n; i++) {8            String s1 = digits.substring(0, i);9            String s2 = digits.substring(i);10 11            List<String> list1 = generateValidNumbers(s1);12            List<String> list2 = generateValidNumbers(s2);13 14            if (!list1.isEmpty() && !list2.isEmpty()) {15                for (String x : list1) {16                    for (String y : list2) {17                        result.add("(" + x + ", " + y + ")");18                    }19                }20            }21        }22        return result;23    }24 25    private List<String> generateValidNumbers(String t) {26        List<String> res = new ArrayList<>();27        int n = t.length();28        if (n == 0) {29            return res;30        }31 32        // Case 1: Integer33        if (isValidInteger(t)) {34            res.add(t);35        }36 37        // Case 2: Decimal38        for (int i = 1; i < n; i++) {39            String intPart = t.substring(0, i);40            String fracPart = t.substring(i);41            if (isValidInteger(intPart) && isValidFractional(fracPart)) {42                res.add(intPart + "." + fracPart);43            }44        }45        return res;46    }47 48    private boolean isValidInteger(String s) {49        // Not a valid integer if it has a leading zero (and is not "0")50        return s.length() <= 1 || s.charAt(0) != '0';51    }52 53    private boolean isValidFractional(String s) {54        // Not a valid fractional part if it has a trailing zero55        return s.charAt(s.length() - 1) != '0';56    }57}

Complexity

Time

O(N^4), where N is the length of the digit string. The main loop runs N-1 times. Inside, generating possibilities for a substring of length k takes O(k^2). Combining results from two lists of size O(i) and O(N-i) takes O(i * (N-i) * N) time. The total time is dominated by this combination step, summing to O(N^4).

Space

O(N^4), where N is the length of the digit string. The output list can contain O(N^3) coordinate strings, each of length O(N).

Trade-offs

Pros

It's a straightforward and easy-to-understand implementation that correctly covers all cases.
The logic directly translates the problem statement into code.

Cons

It can be inefficient for inputs where the same substring is processed multiple times in different splits (e.g., in (1212)).
The time and space complexity are polynomial of a high degree, which might be a concern for larger constraints, though it's acceptable for this problem.

This approach enhances the brute-force method by adding a layer of caching, or memoization. The function that generates valid number representations for a string, generateValidNumbers, can be called with the same substring multiple times for certain inputs. By storing the results of this function in a cache (like a hash map), we can avoid redundant computations and retrieve the pre-computed result instantly.

Algorithm

Initialize a cache (e.g., HashMap<String, List<String>> memo).
Extract the digit string digits from s. Let its length be n.
Initialize an empty list result.
Iterate i from 1 to n-1 to define the split point.
Let s1 = digits.substring(0, i) and s2 = digits.substring(i).
Call a memoized generateValidNumbers(s1) to get list1.
Call a memoized generateValidNumbers(s2) to get list2.
For each x in list1 and y in list2, add "(x, y)" to result.
Return result.

Walkthrough

The overall structure is the same as the brute-force approach: split the digit string, generate possibilities for each part, and combine them. The key difference is in the generateValidNumbers helper function. We introduce a cache, typically a HashMap, to store the results. When generateValidNumbers is called with a string t, it first checks if t exists as a key in our cache. If it does, the cached list of valid numbers is returned immediately. If not, the function computes the list as usual. Before returning the newly computed list, it stores it in the cache with t as the key. This ensures that for any given substring, the expensive computation is performed only once. For subsequent calls with the same substring, the result is fetched in nearly constant time.

1class Solution {2    private Map<String, List<String>> memo = new HashMap<>();3 4    public List<String> ambiguousCoordinates(String s) {5        List<String> result = new ArrayList<>();6        String digits = s.substring(1, s.length() - 1);7        int n = digits.length();8 9        for (int i = 1; i < n; i++) {10            String s1 = digits.substring(0, i);11            String s2 = digits.substring(i);12 13            List<String> list1 = generateValidNumbers(s1);14            List<String> list2 = generateValidNumbers(s2);15 16            if (!list1.isEmpty() && !list2.isEmpty()) {17                for (String x : list1) {18                    for (String y : list2) {19                        result.add("(" + x + ", " + y + ")");20                    }21                }22            }23        }24        return result;25    }26 27    private List<String> generateValidNumbers(String t) {28        if (memo.containsKey(t)) {29            return memo.get(t);30        }31 32        List<String> res = new ArrayList<>();33        int n = t.length();34        if (n == 0) {35            return res;36        }37 38        // Case 1: Integer39        if (isValidInteger(t)) {40            res.add(t);41        }42 43        // Case 2: Decimal44        for (int i = 1; i < n; i++) {45            String intPart = t.substring(0, i);46            String fracPart = t.substring(i);47            if (isValidInteger(intPart) && isValidFractional(fracPart)) {48                res.add(intPart + "." + fracPart);49            }50        }51        52        memo.put(t, res);53        return res;54    }55 56    private boolean isValidInteger(String s) {57        return s.length() <= 1 || s.charAt(0) != '0';58    }59 60    private boolean isValidFractional(String s) {61        return s.charAt(s.length() - 1) != '0';62    }63}

Complexity

Time

O(N^4) in the worst case. The number of unique substrings is O(N^2). Computing `generateValidNumbers` for all of them and storing in the cache takes O(N^4). The main loop then uses these cached results. While the asymptotic complexity is the same, the practical runtime is often better.

Space

O(N^4). The cache can store O(N^2) entries. Each entry can be a list of O(k) strings of length O(k), leading to O(k^2) space per entry. Summing over all substrings, the cache can take up to O(N^4) space. The output list also requires O(N^4) space.

Trade-offs

Pros

Improves performance significantly for inputs with repeating substrings by avoiding redundant work.
Maintains the correctness and relative simplicity of the brute-force approach.

Cons

Worst-case time and space complexity remain the same as the non-memoized version, as there's no benefit for inputs with all unique substrings.
Introduces a small overhead due to the cache management (hash map operations).

Solutions

Solution

1class Solution {2public3  List<String> ambiguousCoordinates(String s) {4    int n = s.length();5    List<String> ans = new ArrayList<>();6    for (int i = 2; i < n - 1; ++i) {7      for (String x : f(s, 1, i)) {8        for (String y : f(s, i, n - 1)) {9          ans.add(String.format("(%s, %s)", x, y));10        }11      }12    }13    return ans;14  }15private16  List<String> f(String s, int i, int j) {17    List<String> res = new ArrayList<>();18    for (int k = 1; k <= j - i; ++k) {19      String l = s.substring(i, i + k);20      String r = s.substring(i + k, j);21      boolean ok = ("0".equals(l) || !l.startsWith("0")) && !r.endsWith("0");22      if (ok) {23        res.add(l + (k < j - i ? "." : "") + r);24      }25    }26    return res;27  }28}

1class Solution {2public:3  vector<string> ambiguousCoordinates(string s) {4    int n = s.size();5    vector<string> ans;6    auto f = [&](int i, int j) {7      vector<string> res;8      for (int k = 1; k <= j - i; ++k) {9        string l = s.substr(i, k);10        string r = s.substr(i + k, j - i - k);11        bool ok = (l == "0" || l[0] != '0') && r.back() != '0';12        if (ok) {13          res.push_back(l + (k < j - i ? "." : "") + r);14        }15      }16      return res;17    };18    for (int i = 2; i < n - 1; ++i) {19      for (auto &x : f(1, i)) {20        for (auto &y : f(i, n - 1)) {21          ans.emplace_back("(" + x + ", " + y + ")");22        }23      }24    }25    return ans;26  }27};

1class Solution:2    def ambiguousCoordinates(self, s: str) -> List[str]: def f(i, j): res = [] for k in range(1, j - i + 1): l, r = s[i: i + k], s[i + k: j] ok = (l == '0' or not l . startswith('0')) and not r . endswith('0') if ok: res . append(l + ('.' if k < j - i else '') + r) return res n = len(s) return [f '( { x } , { y } )' for i in range(2, n - 1) for x in f(1, i) for y in f(i, n - 1)]

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem