algoadvance

Leetcode 816. Ambiguous Coordinates

Problem Statement

We are given a string s representing a pair of coordinates (x, y) as (x, y) in a 2D plane. The string s does not contain any spaces and has the form "(abc)", where abc is a string containing digits (0-9) except it will not contain any leading zeros unless the digit itself is 0.

We need to generate all possible interpretations of (x, y) by adding decimal points into abc such that both x and y do not have any leading zeros or unnecessary trailing zeros.

For example, if the input is "(123)", the possible interpretations could be:

Clarifying Questions

  1. What is the maximum length of the string s?
  2. Are we guaranteed that the string s will always be in the valid format of a coordinate pair?

These questions help in determining the edge cases and constraints.

Strategy

  1. Extract the digits string abc from the input string s.
  2. Generate valid split points for x and y:
    • Iterate over possible split points in the string abc.
    • For each split point, try breaking the string into x and y.
  3. Generate possible valid decimal representations:
    • For each substring part (x and y), generate all valid decimal representations without leading or trailing zeros.
    • Check conditions to ensure valid number formatting.
  4. Combine all valid pairs of (x, y) generated and return them as a list.

Code

import java.util.ArrayList;
import java.util.List;

public class AmbiguousCoordinates {
    
    public List<String> ambiguousCoordinates(String s) {
        List<String> result = new ArrayList<>();
        // Remove the parentheses
        String digits = s.substring(1, s.length() - 1);
        
        // Generate all possible split points
        for (int i = 1; i < digits.length(); i++) {
            String xPart = digits.substring(0, i);
            String yPart = digits.substring(i);
            
            List<String> xCandidates = generateValidNumbers(xPart);
            List<String> yCandidates = generateValidNumbers(yPart);
            
            for (String x : xCandidates) {
                for (String y : yCandidates) {
                    result.add("(" + x + ", " + y + ")");
                }
            }
        }
        
        return result;
    }

    private List<String> generateValidNumbers(String s) {
        List<String> validNumbers = new ArrayList<>();
        
        // Directly valid integer
        if (isValidInteger(s)) {
            validNumbers.add(s);
        }
        
        // Insert decimal points and validate them
        for (int i = 1; i < s.length(); i++) {
            String left = s.substring(0, i);
            String right = s.substring(i);
            if (isValidDecimal(left, right)) {
                validNumbers.add(left + "." + right);
            }
        }
        return validNumbers;
    }
    
    private boolean isValidInteger(String s) {
        // Single character or doesn't start with 0 (except for "0" itself)
        return s.length() == 1 || s.charAt(0) != '0';
    }
    
    private boolean isValidDecimal(String left, String right) {
        // Left part should be valid integer and right part should not end with 0
        return isValidInteger(left) && !right.endsWith("0");
    }

    public static void main(String[] args) {
        AmbiguousCoordinates ac = new AmbiguousCoordinates();
        System.out.println(ac.ambiguousCoordinates("(123)"));
        System.out.println(ac.ambiguousCoordinates("(00011)"));
        System.out.println(ac.ambiguousCoordinates("(0123)"));
        System.out.println(ac.ambiguousCoordinates("(100)"));
    }
}

Time Complexity

Overall, the time complexity is approximately O(n^2) where n is the length of the string as in most cases m will be close to n.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI