LeetCode_字符串_中等_816.模糊坐标

蔚落 2023-10-07 20:59 58阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 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 是不被允许的。

**提示：**  
4 <= S.length <= 12.  
S\[0\] = “(”, S\[S.length - 1\] = “)”, 且字符串 S 中的其他元素都是数字。

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/ambiguous-coordinates

## 2.思路 ##

（1）穷举法  
思路参考[本题官方题解][Link 1]。具体细节见下方代码中的注释。

## 3.代码实现（Java） ##

//思路1————穷举法
    class Solution {
        
        public List<String> ambiguousCoordinates(String s) {
        
            List<String> res = new ArrayList<>();
            // 去掉 s 首尾的括号
            int length = s.length() - 2;
            s = s.substring(1, s.length() - 1);
            for (int left = 1; left < length; left++) {
        
                //获取符合题目条件的左边的数字集合
                List<String> leftD = getPos(s.substring(0, left));
                if (leftD.isEmpty()) {
        
                    continue;
                }
                //获取符合题目条件的右边的数字集合
                List<String> rightD = getPos(s.substring(left));
                if (rightD.isEmpty()) {
        
                    continue;
                }
                //拼接左右两个数字的所有可能情况，并将结果保存到 res 中
                for (String i : leftD) {
        
                    for (String j : rightD) {
        
                        //注意两个数字中间（逗号之后）有一个空格
                        res.add("(" + i + ", " + j + ")");
                    }
                }
            }
            return res;
        }
        
        public List<String> getPos(String s) {
        
            List<String> pos = new ArrayList<>();
            //考虑 s 以 '0' 开头或其本身就是 "0" 的情况
            if (s.charAt(0) != '0' || "0".equals(s)) {
        
                pos.add(s);
            }
            for (int p = 1; p < s.length(); p++) {
        
                if ((p != 1 && s.charAt(0) == '0') || s.charAt(s.length() - 1) == '0') {
        
                    continue;
                }
                pos.add(s.substring(0, p) + "." + s.substring(p));
            }
            return pos;
        }
    }

[Link 1]: https://leetcode.cn/problems/ambiguous-coordinates/solution/mo-hu-zuo-biao-by-leetcode-solution-y1yz/