Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/816.html
816. Ambiguous Coordinates
Level
Medium
Description
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: “(123)”
Output: [“(1, 23)”, “(12, 3)”, “(1.2, 3)”, “(1, 2.3)”]
Example 2:
Input: “(00011)”
Output: [“(0.001, 1)”, “(0, 0.011)”]
Explanation:
0.0, 00, 0001 or 00.01 are not allowed.
Example 3:
Input: “(0123)”
Output: [“(0, 123)”, “(0, 12.3)”, “(0, 1.23)”, “(0.1, 23)”, “(0.1, 2.3)”, “(0.12, 3)”]
Example 4:
Input: “(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 inSare digits.
Solution
For the given string S, consider all the digits and consider all the indices where a comma can be inserted. If there are n digits in S, then there are n - 1 insertion points in S. Inserting a comma at an insertion point splits the digits into two parts. For each part, consider all possible numbers.
For the given part, the possible numbers are as follows.
- If the part has length 1, or the first (or leftmost/highest) digit is not zero, then the part can be an integer without adding a decimal point.
- If the part has length greater than 1 and all the digits are zeros, then no possible numbers can be obtained from the part.
- If the last (or rightmost/lowest) digit is zero, then no decimal point can be added, and the only possible number is the part without adding a decimal point.
- If the last digit is not zero, then check whether there are leading zeros. If there are no leading zeros, then a decimal point can be inserted between any two digits. If there are leading zeros (at least one leading zero), then a decimal point can only be inserted after the first digit.
For each insertion point where a comma is inserted such that the string is split into two parts, apply the rules for both parts to obtain all possible coordinates. Finally, return the list that stores all possible coordinates.
-
class Solution { public List<String> ambiguousCoordinates(String S) { List<String> coordinatesList = new ArrayList<String>(); int length = S.length(); int left = 1, right = length - 1; for (int i = left + 1; i < right; i++) { String xCoordinateStr = S.substring(left, i); String yCoordinateStr = S.substring(i, right); List<String> xCoordinatesList = getPossibleCoordinates(xCoordinateStr); List<String> yCoordinatesList = getPossibleCoordinates(yCoordinateStr); for (String xCoordinate : xCoordinatesList) { for (String yCoordinate : yCoordinatesList) { String coordinate = "(" + xCoordinate + ", " + yCoordinate + ")"; coordinatesList.add(coordinate); } } } return coordinatesList; } public List<String> getPossibleCoordinates(String coordinateStr) { List<String> coordinatesList = new ArrayList<String>(); if (coordinateStr.length() == 1 || coordinateStr.charAt(0) != '0') coordinatesList.add(coordinateStr); int leadingZeros = 0; int length = coordinateStr.length(); for (int i = 0; i < length; i++) { if (coordinateStr.charAt(i) == '0') leadingZeros++; else break; } if (leadingZeros < length && coordinateStr.charAt(length - 1) != '0') { int maxInsertionIndex = leadingZeros > 0 ? 1 : length - 1; for (int i = 1; i <= maxInsertionIndex; i++) { StringBuffer sb = new StringBuffer(coordinateStr); sb.insert(i, '.'); coordinatesList.add(sb.toString()); } } return coordinatesList; } } -
// OJ: https://leetcode.com/problems/ambiguous-coordinates/ // Time: O(N^3) // Space: O(N) class Solution { vector<string> getNumbers(string s) { if (s[0] == '0') { if (s.size() == 1) return { s }; if (s.back() == '0') return {}; s.insert(begin(s) + 1, '.'); return { s }; } if (s.back() == '0') return { s }; vector<string> ans; ans.push_back(s); for (int i = 1; i <= s.size() - 1; ++i) { auto tmp = s; tmp.insert(begin(tmp) + i, '.'); ans.push_back(tmp); } return ans; } public: vector<string> ambiguousCoordinates(string s) { vector<string> ans; for (int i = 2, N = s.size(); i < N - 1; ++i) { auto first = getNumbers(s.substr(1, i - 1)); if (first.empty()) continue; auto second = getNumbers(s.substr(i, N - 1 - i)); if (second.empty()) continue; for (auto &a : first) { for (auto &b : second) { ans.push_back("(" + a + ", " + b + ")"); } } } return ans; } }; -
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) ] ############ class Solution(object): def ambiguousCoordinates(self, S): """ :type S: str :rtype: List[str] """ ans = [] S = S[1:-1] for i in range(1, len(S)): left, right = S[:i], S[i:] left_list = self.get_number(left) right_list = self.get_number(right) if left_list and right_list: for left_number in left_list: for right_number in right_list: ans.append("(" + left_number + ", " + right_number + ")") return ans def get_number(self, num): decimal_list = [] if len(num) == 1 or num[0] != '0': decimal_list.append(num) for i in range(1, len(num)): integer, fractor = num[:i], num[i:] print(integer, fractor) if (len(integer) > 1 and integer[0] == '0') or fractor[-1] == '0': continue decimal_list.append(integer + '.' + fractor) return decimal_list -
func ambiguousCoordinates(s string) []string { f := func(i, j int) []string { res := []string{} for k := 1; k <= j-i; k++ { l, r := s[i:i+k], s[i+k:j] ok := (l == "0" || l[0] != '0') && (r == "" || r[len(r)-1] != '0') if ok { t := "" if k < j-i { t = "." } res = append(res, l+t+r) } } return res } n := len(s) ans := []string{} for i := 2; i < n-1; i++ { for _, x := range f(1, i) { for _, y := range f(i, n-1) { ans = append(ans, "("+x+", "+y+")") } } } return ans } -
function ambiguousCoordinates(s: string): string[] { s = s.slice(1, s.length - 1); const n = s.length; const dfs = (s: string) => { const res: string[] = []; for (let i = 1; i < s.length; i++) { const t = `${s.slice(0, i)}.${s.slice(i)}`; if (`${Number(t)}` === t) { res.push(t); } } if (`${Number(s)}` === s) { res.push(s); } return res; }; const ans: string[] = []; for (let i = 1; i < n; i++) { for (const left of dfs(s.slice(0, i))) { for (const right of dfs(s.slice(i))) { ans.push(`(${left}, ${right})`); } } } return ans; }