Java | Backtracking | Explained
Idea:\n Consider all possible non-empty breakdowns of s\n Put decimal in both parts in every possible place and check if the output is valid\n If valid, then ad
**Idea:**\n* Consider all possible non-empty breakdowns of s\n* Put decimal in both parts in every possible place and check if the output is valid\n* If valid, then add them to the result\n* For validity:\n\t* If a number doesn\'t have a decimal, then it should either be 0 or not have a leading 0\n\t* Else if a number has decimal, then\n\t\t* the whole number part should either be 0 or not have a leading 0\n\t\t* the fraction part mustn\'t have a trailing 0\n>**T/S:** O()/O(), where n = size(s)\n```\nprivate static final String ZERO = "0";\n\npublic List<String> ambiguousCoordinates(String s) {\n\ts = s.substring(1, s.length() - 1);\n\tvar n = s.length();\n\tvar coordinates = new ArrayList<String>();\n\n\tfor (var i = 1; i < n; i++)\n\t\tbacktrack(s.substring(0, i), s.substring(i), coordinates);\n\n\treturn coordinates;\n}\n\nprivate void backtrack(String x, String y, List<String> coordinates) {\n\tvar xCoordinates = putDecimal(x);\n\tvar yCoordinates = putDecimal(y);\n\n\tfor (var xCoordinate : xCoordinates) {\n\t\tif (isInvalid(xCoordinate))\n\t\t\tcontinue;\n\n\t\tfor (var yCoordinate : yCoordinates) {\n\t\t\tif (isInvalid(yCoordinate))\n\t\t\t\tcontinue;\n\t\t\tcoordinates.add("(%s, %s)".formatted(xCoordinate, yCoordinate));\n\t\t}\n\t}\n}\n\nprivate List<String> putDecimal(String s) {\n\tvar decimals = new ArrayList<>(List.of(s));\n\n\tfor (var i = 1; i < s.length(); i++)\n\t\tdecimals.add("%s.%s".formatted(s.substring(0, i), s.substring(i)));\n\n\treturn decimals;\n}\n\nprivate boolean isInvalid(String s) {\n\tvar decimalIndex = s.indexOf(\'.\');\n\n\tif (decimalIndex == -1)\n\t\treturn !s.equals(ZERO) && s.startsWith(ZERO);\n\n\tvar wholePart = s.substring(0, decimalIndex);\n\tif (!wholePart.equals(ZERO) && wholePart.startsWith(ZERO))\n\t\treturn true;\n\n\tvar fractionPart = s.substring(decimalIndex + 1);\n\treturn fractionPart.endsWith(ZERO);\n}\n```\n***Please upvote if this helps***
['Java']