0816. Ambiguous Coordinates - kumaeki/LeetCode GitHub Wiki

0816. Ambiguous Coordinates

We had some 2-dimensional coordinates, like "(1, 3)" or "(2, 0.5)". Then, we removed all commas, decimal points, and spaces, and ended up with the string s. Return a list of strings representing all possibilities for what our original coordinates could have been.

Our original representation never had extraneous zeroes, so we never started with numbers like "00", "0.0", "0.00", "1.0", "001", "00.01", or any other number that can be represented with less digits. Also, a decimal point within a number never occurs without at least one digit occuring before it, so we never started with numbers like ".1".

The final answer list can be returned in any order. Also note that all coordinates in the final answer have exactly one space between them (occurring after the comma.)

Example 1:

Input: s = "(123)"
Output: ["(1, 23)", "(12, 3)", "(1.2, 3)", "(1, 2.3)"]

Example 2:

Input: s = "(00011)"
Output:  ["(0.001, 1)", "(0, 0.011)"]
Explanation: 
0.0, 00, 0001 or 00.01 are not allowed.

Example 3:

Input: s = "(0123)"
Output: ["(0, 123)", "(0, 12.3)", "(0, 1.23)", "(0.1, 23)", "(0.1, 2.3)", "(0.12, 3)"]

Example 4:

Input: s = "(100)"
Output: [(10, 0)]
Explanation: 
1.0 is not allowed.

Note:

  • 4 <= s.length <= 12.
  • s[0] = "(", s[s.length - 1] = ")", and the other elements in s are digits.

解法1

其实很讨厌这种问题,会有很多边边角角的地方需要注意. 但是对于比单纯的算法问题, 这类问题反而是实际开发过程中有更大的概率遇到.

既然最大只有12位, 那就穷举好了. 需要注意的是以下 3 种情况

  1. 当前后都是0的时候,无法得到有效的数字
  2. 当第一位是0的时候(最后一位不是0), 必须要把小数点放在第二位才能得到唯一的有效数字
  3. 当最后一位是0的时候(第一位不是0), 不能插入小数点
class Solution {
    public List<String> ambiguousCoordinates(String s) {
        List<String> res = new ArrayList<String>();
        
        // 遍历所有可能的分割方式
        for(int i = 2, len = s.length(); i < len - 1; i++)
            helper(res, s.substring(1, i), s.substring(i, len - 1));

        return res;
    }
    
    // 对于子字符串string1 和 string2, 通过组合他们的所有可能组合得到结果
    private void helper(List<String> res, String string1, String string2){
        List<String> l1 = getListWithPoint(string1), l2 = getListWithPoint(string2);
        // 如果s1 或者 s2 无法得到有效数字, 结束运算
        if(l1 == null || l2 == null)
            return ;
        
        for(String s1: l1)
            for(String s2: l2)
                res.add("("+ s1 +", " + s2 +")");
        
    }
    
    // 对于每次分割出来的子字符,得到可能的所有数字的list
    private List<String> getListWithPoint(String str){
        
        int len = str.length();
        // 前后同时出现0, 返回null
        if(len > 1 && str.charAt(0) == '0' && str.charAt(len - 1) == '0')
            return null;
        
        List<String> list = new ArrayList<String>();

        // 最后一位是0 (1230),或者长度为1, 就不能加入小数点
        if(str.charAt(len - 1) == '0'  || len == 1){
            list.add(str);
            return list;
        }
            
        // 第一位是0 (0123), 只有在第一位后面加小数点一种可能
        if(str.charAt(0) == '0'){
            list.add(str.substring(0,1) + '.' + str.substring(1));
            return list;
        }
        
        // 除此之外,都可以任意的加小数点
        list.add(str);
        for(int i = 1; i < len; i++)
            list.add(str.substring(0, i) + "." + str.substring(i));
        
        return list;
    }
}
⚠️ **GitHub.com Fallback** ⚠️