# Ambiguous Coordinates
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/ambiguous-coordinates)
Canonical: https://scaleengineer.com/dsa/problems/ambiguous-coordinates
**Patterns:** [Backtracking](https://scaleengineer.com/dsa/patterns/backtracking), [Enumeration](https://scaleengineer.com/dsa/patterns/enumeration)
**Data structures:** String
---
## Problem
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
## Brute Force Enumeration
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.
**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).
**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.
### Explanation
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`:
1.  **Integer:** `t` is a valid integer if it's "0" or doesn't start with '0'.
2.  **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.
```java
class Solution {
    public List<String> ambiguousCoordinates(String s) {
        List<String> result = new ArrayList<>();
        String digits = s.substring(1, s.length() - 1);
        int n = digits.length();

        for (int i = 1; i < n; i++) {
            String s1 = digits.substring(0, i);
            String s2 = digits.substring(i);

            List<String> list1 = generateValidNumbers(s1);
            List<String> list2 = generateValidNumbers(s2);

            if (!list1.isEmpty() && !list2.isEmpty()) {
                for (String x : list1) {
                    for (String y : list2) {
                        result.add("(" + x + ", " + y + ")");
                    }
                }
            }
        }
        return result;
    }

    private List<String> generateValidNumbers(String t) {
        List<String> res = new ArrayList<>();
        int n = t.length();
        if (n == 0) {
            return res;
        }

        // Case 1: Integer
        if (isValidInteger(t)) {
            res.add(t);
        }

        // Case 2: Decimal
        for (int i = 1; i < n; i++) {
            String intPart = t.substring(0, i);
            String fracPart = t.substring(i);
            if (isValidInteger(intPart) && isValidFractional(fracPart)) {
                res.add(intPart + "." + fracPart);
            }
        }
        return res;
    }

    private boolean isValidInteger(String s) {
        // Not a valid integer if it has a leading zero (and is not "0")
        return s.length() <= 1 || s.charAt(0) != '0';
    }

    private boolean isValidFractional(String s) {
        // Not a valid fractional part if it has a trailing zero
        return s.charAt(s.length() - 1) != '0';
    }
}
```
### 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`.

## Optimized Brute Force with Memoization
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.
**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.
**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).
### Explanation
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.
```java
class Solution {
    private Map<String, List<String>> memo = new HashMap<>();

    public List<String> ambiguousCoordinates(String s) {
        List<String> result = new ArrayList<>();
        String digits = s.substring(1, s.length() - 1);
        int n = digits.length();

        for (int i = 1; i < n; i++) {
            String s1 = digits.substring(0, i);
            String s2 = digits.substring(i);

            List<String> list1 = generateValidNumbers(s1);
            List<String> list2 = generateValidNumbers(s2);

            if (!list1.isEmpty() && !list2.isEmpty()) {
                for (String x : list1) {
                    for (String y : list2) {
                        result.add("(" + x + ", " + y + ")");
                    }
                }
            }
        }
        return result;
    }

    private List<String> generateValidNumbers(String t) {
        if (memo.containsKey(t)) {
            return memo.get(t);
        }

        List<String> res = new ArrayList<>();
        int n = t.length();
        if (n == 0) {
            return res;
        }

        // Case 1: Integer
        if (isValidInteger(t)) {
            res.add(t);
        }

        // Case 2: Decimal
        for (int i = 1; i < n; i++) {
            String intPart = t.substring(0, i);
            String fracPart = t.substring(i);
            if (isValidInteger(intPart) && isValidFractional(fracPart)) {
                res.add(intPart + "." + fracPart);
            }
        }
        
        memo.put(t, res);
        return res;
    }

    private boolean isValidInteger(String s) {
        return s.length() <= 1 || s.charAt(0) != '0';
    }

    private boolean isValidFractional(String s) {
        return s.charAt(s.length() - 1) != '0';
    }
}
```
### 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`.

# Solutions
### Java

```java
class Solution {
public
  List<String> ambiguousCoordinates(String s) {
    int n = s.length();
    List<String> ans = new ArrayList<>();
    for (int i = 2; i < n - 1; ++i) {
      for (String x : f(s, 1, i)) {
        for (String y : f(s, i, n - 1)) {
          ans.add(String.format("(%s, %s)", x, y));
        }
      }
    }
    return ans;
  }
private
  List<String> f(String s, int i, int j) {
    List<String> res = new ArrayList<>();
    for (int k = 1; k <= j - i; ++k) {
      String l = s.substring(i, i + k);
      String r = s.substring(i + k, j);
      boolean ok = ("0".equals(l) || !l.startsWith("0")) && !r.endsWith("0");
      if (ok) {
        res.add(l + (k < j - i ? "." : "") + r);
      }
    }
    return res;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<string> ambiguousCoordinates(string s) {
    int n = s.size();
    vector<string> ans;
    auto f = [&](int i, int j) {
      vector<string> res;
      for (int k = 1; k <= j - i; ++k) {
        string l = s.substr(i, k);
        string r = s.substr(i + k, j - i - k);
        bool ok = (l == "0" || l[0] != '0') && r.back() != '0';
        if (ok) {
          res.push_back(l + (k < j - i ? "." : "") + r);
        }
      }
      return res;
    };
    for (int i = 2; i < n - 1; ++i) {
      for (auto &x : f(1, i)) {
        for (auto &y : f(i, n - 1)) {
          ans.emplace_back("(" + x + ", " + y + ")");
        }
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    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)]

```