模糊坐标

1.题目描述

我们有一些二维坐标，如 "(1, 3)" 或 "(2, 0.5)"，然后我们移除所有逗号，小数点和空格，得到一个字符串S。返回所有可能的原始字符串到一个列表中。

原始的坐标表示法不会存在多余的零，所以不会出现类似于"00", "0.0", "0.00", "1.0", "001", "00.01"或一些其他更小的数来表示坐标。此外，一个小数点前至少存在一个数，所以也不会出现“.1”形式的数字。

最后返回的列表可以是任意顺序的。而且注意返回的两个数字中间（逗号之后）都有一个空格。

示例1：

输入: "(123)" 输出: ["(1, 23)", "(12, 3)", "(1.2, 3)", "(1, 2.3)"]

示例2：

输入: "(00011)" 输出: ["(0.001, 1)", "(0, 0.011)"] 解释: 0.0, 00, 0001 或 00.01 是不被允许的。

示例3：

输入: "(0123)" 输出: ["(0, 123)", "(0, 12.3)", "(0, 1.23)", "(0.1, 23)", "(0.1, 2.3)", "(0.12, 3)"]

示例4：

输入: "(100)" 输出: [(10, 0)] 解释: 1.0 是不被允许的。

2.分析

分析题目后，我们需要将给定的字符串转化为二维坐标，并且该坐标中可能还包含'.'。实际上，这可以看作是两种组合情况：

• 将坐标的前半部分与后半部分组合。
• 将前半部分加上'.'，或将后半部分加上'.'。

对于坐标的划分，实际上是将字符串分为两部分，一部分在前面，另一部分在后面。我们可以通过直接截取子串来实现这个划分，然后对前后两部分分别进行回溯操作，尝试将'.'添加进去。获得两部分的结果后，我们需要将前部分的每个结果与后部分的每个结果进行组合，最终得到所有可能的正确答案。

3.代码

class Solution {
    List<String> ans;
    HashSet<String> set;
    List<String> list;
    int n;
    public List<String> ambiguousCoordinates(String s) {
        ans = new ArrayList<>();
        set = new HashSet<>();
        String str = s.substring(1, s.length() - 1);
        n = str.length();
        for(int i = 1; i < n; i++){
            // 截取两部分的字符串
            String str1 = str.substring(0, i);
            String str2 = str.substring(i, n);
            StringBuilder sb = new StringBuilder();
            list = new ArrayList<>();
            // 对第一部分进行回溯
            backTrack(str1, sb, 0);
            List<String> list1 = new ArrayList<>(list);
            list.clear();
            sb = new StringBuilder();
            // 对第二部分进行回溯
            backTrack(str2, sb, 0);
            List<String> list2 = new ArrayList<>(list);
            // 第一部分和第二部分进行一个组合
            addAns(list1, list2);
        }
        return ans;
    }
    // 回溯代码
    public void backTrack(String str, StringBuilder sb, int start){
        // 当包括'.' 并且长度为原字符串长度+1
        if(sb.indexOf(".") != -1 && sb.length() == str.length() + 1){
            // 都有'.'最后一个数必不能是0
            if(sb.charAt(sb.length() - 1) == '0') return;
            String sub = sb.substring(0, sb.indexOf("."));
            // '.'前面长度大于1但是有前导0 必不可能
            if(sub.length() > 1 && sub.charAt(0) == '0') return;
            list.add(new String(sb));
            return;
        // 没有'.' 并且长度等于原字符串的长度
        }else if(sb.indexOf(".") == -1 && sb.length() == str.length()){
            // 没有'.' 长度大于1 还有前导0 必不可能
            if(sb.length() > 1 && sb.charAt(0) == '0') return;
            list.add(new String(sb));
            return;
        }
        for(int i = start; i < str.length(); i++){
            sb.append(str.charAt(i));
            // 前面出现了两个0 不可能
            if(sb.length() > 1 && sb.charAt(0) == '0' && sb.charAt(1) == '0') continue;
            // 只能添加一个'.'
            if(sb.indexOf(".") == -1 && i != str.length() - 1){
                sb.append(".");
            }
            backTrack(str, sb, i + 1);
            sb.deleteCharAt(sb.length() - 1);
        }
    }
    // 组合两部分的结果
    public void addAns(List<String> list1, List<String> list2){
        for(String l1 : list1){
            for(String l2 : list2){
                String curStr = "(" + l1 + ", " + l2 + ")";
                if(set.contains(curStr)){
                    continue;
                }
                set.add(curStr);
                ans.add(curStr);
            }
        }
    }
    
}