816. Ambiguous Coordinates #

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. 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 less digits. Also, a decimal point within a number never occurs without at least one digit occuring before it, so we never started with numbers like “.1”.

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

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

Example 2:Input: s = "(00011)"
Output:  ["(0.001, 1)", "(0, 0.011)"]
Explanation:
0.0, 00, 0001 or 00.01 are not allowed.

Example 3:Input: s = "(0123)"
Output: ["(0, 123)", "(0, 12.3)", "(0, 1.23)", "(0.1, 23)", "(0.1, 2.3)", "(0.12, 3)"]

Example 4:Input: s = "(100)"
Output: [(10, 0)]
Explanation:
1.0 is not allowed.

Note:

4 <= s.length <= 12.
s[0] = “(", s[s.length - 1] = “)”, and the other elements in s are digits.

Problem Summary #

We have some two-dimensional coordinates, such as “(1, 3)” or “(2, 0.5)”, and then we remove all commas, decimal points, and spaces to get a string S. Return all possible original strings in a list. The original coordinate representation will not have extra zeros, so numbers like “00”, “0.0”, “0.00”, “1.0”, “001”, “00.01”, or some other coordinate representations that can be written with fewer digits will not appear. In addition, there must be at least one digit before a decimal point, so numbers in the form “.1” will also not appear.

The final returned list can be in any order. Also note that there is a space between the two returned numbers (after the comma).

Solution Approach #

This problem does not involve much algorithmic thinking; it is a pure brute-force problem. First split the original string into two parts, then move the decimal point in each of the two substrings, and finally combine each case again. This completes one split. Split the original string at every position according to this pattern, and the problem is solved.
There are 2 points to pay attention to in this problem. The first is the final output string. Please note that there is a space between the two numbers (after the comma). Failing to follow the output format requirement will also lead to Wrong Answer. The other point is that when splitting numbers, there are 2 kinds of invalid cases: one with a leading 0, and the other with a trailing 0. The leading-0 case is also divided into 2 cases. One is when there is only one digit, that is, only a single 0. This case can be returned directly, because no matter how this single 0 is split, there is only one way. The other is when the length is greater than 1, namely the 0xxx case. The 0xxx case has only one splitting method, namely 0.xxx. There is only one way to split a number with a trailing 0, namely xxx0, and it cannot be split, because xxx.0, xx.x0, and x.xx0 are all invalid cases. Therefore, numbers with a trailing 0 can also be returned directly. See the code and comments for the specific implementation.

Code #

package leetcode

func ambiguousCoordinates(s string) []string {
	res := []string{}
	s = s[1 : len(s)-1]
	for i := range s[:len(s)-1] {
		a := build(s[:i+1])
		b := build(s[i+1:])
		for _, ta := range a {
			for _, tb := range b {
				res = append(res, "("+ta+", "+tb+")")
			}
		}
	}
	return res
}

func build(s string) []string {
	res := []string{}
	if len(s) == 1 || s[0] != '0' {
		res = append(res, s)
	}
	// Case ending with 0
	if s[len(s)-1] == '0' {
		return res
	}
	// Case of splitting a length greater than one with a leading 0
	if s[0] == '0' {
		res = append(res, "0."+s[1:])
		return res
	}
	for i := range s[:len(s)-1] {
		res = append(res, s[:i+1]+"."+s[i+1:])
	}
	return res
}