LeetCode 816: Ambiguous Coordinates
Problem Description
Explanation:
To solve this problem, we need to iterate through all possible ways of splitting the input string s into two parts such that each part can represent a valid coordinate. We then generate valid coordinate representations for each split and add them to the result list.
- Iterate through all possible splits of the input string
s. - For each split, generate all possible valid coordinate representations for the two parts.
- Check for valid formats and add them to the result list.
Time Complexity: O(n^3) where n is the length of the input string s.
Space Complexity: O(n) for storing the result list.
:
Solutions
class Solution {
public List<String> ambiguousCoordinates(String s) {
List<String> result = new ArrayList<>();
for (int i = 2; i < s.length() - 1; i++) {
List<String> leftCoords = generateCoordinates(s.substring(1, i));
List<String> rightCoords = generateCoordinates(s.substring(i, s.length() - 1));
for (String left : leftCoords) {
for (String right : rightCoords) {
result.add("(" + left + ", " + right + ")");
}
}
}
return result;
}
private List<String> generateCoordinates(String str) {
List<String> coordinates = new ArrayList<>();
if (str.length() == 1 || !str.startsWith("0")) {
coordinates.add(str);
}
for (int i = 1; i < str.length(); i++) {
String left = str.substring(0, i);
String right = str.substring(i);
if ((!left.startsWith("0") || left.equals("0")) && !right.endsWith("0")) {
coordinates.add(left + "." + right);
}
}
return coordinates;
}
}Related LeetCode Problems
Loading editor...