leetcode 816. Ambiguous Coordinates | 816. 模糊坐标（Java）

题目

https://leetcode.com/problems/ambiguous-coordinates/

题解

related topics 说是回溯，我偷了个懒，每次都 new 一个新的 String，就不用回溯了。

思路是：把字符串分割成左右两边，分别生成左 list 和右 list，然后左右 list 两两组合。

class Solution {
    public List<String> ambiguousCoordinates(String s) {
        StringBuilder num = new StringBuilder(s.substring(1, s.length() - 1));
        List<String> result = new ArrayList<>();
        // 把num分成左右两半，分别拿到所有可能的数字，然后两两组合
        for (int i = 1; i < num.length(); i++) {
            List<String> left = getList(new StringBuilder(num.substring(0, i)));
            List<String> right = getList(new StringBuilder(num.substring(i, num.length())));
            for (String l : left) {
                for (String r : right) {
                    result.add("(" + l + ", " + r + ")");
                }
            }
        }
        return result;
    }

    // 给字符串s加小数点，返回所有可能的结果
    public List<String> getList(StringBuilder s) {
        List<String> result = new ArrayList<>();
        for (int i = 1; i < s.length(); i++) {
            String cur = new StringBuilder(s).insert(i, ".").toString();
            if (isValid(cur)) result.add(cur);
        }
        if (isValid(s.toString())) result.add(s.toString());
        return result;
    }

    public boolean isValid(String s) {
        if (s.startsWith("00") || s.startsWith(".")) return false;
        if (s.contains(".") && s.endsWith("0")) return false;
        // 只要以0开头，所有后面不是小数点的字符串，都是耍流氓
        if (s.length() > 1 && s.startsWith("0") && s.charAt(1) != '.') return false;
        return true;
    }
}