We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Ambiguous Coordinates

Number: 834

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

Given a coordinate string s that has had commas, decimal points, and spaces removed (for example, "(1, 3)" becomes "(13)"), return a list of all possible original coordinates. The original coordinates did not have extra leading or trailing zeros and any decimal point always had at least one digit before it. The resulting coordinate strings should be formatted with exactly one space after the comma.

Key Insights

  • Remove the outer parentheses to work with the pure digits.
  • For each valid split of the remaining string into two parts, generate valid representations by inserting a decimal point in all possible positions, while enforcing no extraneous zeros.
  • Validate integer-only representations (ensuring no invalid leading zeros) and those with decimals (ensuring no trailing zeros in the fractional part).
  • Use nested loops: one for splitting the string into the two coordinate parts, and a helper function to determine all valid representations for each part.
  • Combine each valid representation from the left part with each from the right part to form the final coordinate string.

Space and Time Complexity

Time Complexity: O(n^2) in the worst-case scenario, due to iterating through each possible split and potential decimal insertions. Space Complexity: O(n) for temporary storage and output list.

Solution

First, remove the outer parentheses from s. Then, for every possible split of the string into two parts, generate valid numeric representations for each side using a helper function. This helper function generates the integer version (if valid) and attempts to insert a decimal point at various positions where the resulting parts are valid (i.e., checking for invalid leading zeros on the integer part and invalid trailing zeros on the fractional part). Finally, combine valid pairs into formatted coordinate strings.

Code Solutions

def ambiguousCoordinates(s: str) -> [str]:
    # Helper function to generate valid numbers by inserting a decimal in all valid positions.
    def generate_numbers(num_str: str) -> [str]:
        n = len(num_str)
        results = []
        # Check if the entire string forms a valid integer
        if num_str[0] != '0' or num_str == "0":
            results.append(num_str)
        # Try inserting a decimal point in every possible valid position
        for i in range(1, n):
            left = num_str[:i]
            right = num_str[i:]
            # Skip if the integer part has a leading zero (unless it is "0")
            if left[0] == '0' and left != "0":
                continue
            # Skip if the fractional part has trailing zeros
            if right[-1] == '0':
                continue
            results.append(left + "." + right)
        return results

    s = s[1:-1]  # Remove the outer parentheses
    answer = []
    # Split the string into two parts for x and y coordinates
    for i in range(1, len(s)):
        left_part, right_part = s[:i], s[i:]
        left_numbers = generate_numbers(left_part)
        right_numbers = generate_numbers(right_part)
        for left in left_numbers:
            for right in right_numbers:
                # Format the coordinate as requested
                answer.append("(" + left + ", " + right + ")")
    return answer

# Example usage:
print(ambiguousCoordinates("(123)"))
← Back to All Questions