leetcode 93. Restore IP Addresse

ip的每一个由.分割的部分称为字段，例如“12.13.23.34”的四个字段分别为12，13，23和34

思路1

1. dfs每一个字符，对每一个字符，做相应的操作
2. 针对每一个字符，有两种可能：一是作为ip某个字段的最后一位数字，二是作为中间的数字。例如“12.13.23.34”中的第一个1，就是作为中间的数字，而第一个2，是作为字段的结尾数字
3. 如果某个字符不是字段的结尾，就需要把到这个字符为止的字段的值传递到后面。
4. 如果当前字符为0，则必作为字段的结尾。
5. 结束条件：到达字符串的末尾。如果此时没有残缺的字段，并且已有字段为4个，那么当前的4个字段就是结果的一种可能

class Solution(object):
    def restoreIpAddresses(self, s):
        """
        :type s: str
        :rtype: List[str]
        """
        self.ret = []
        self.dfs(0, 0, [], s)
        return self.ret
    
    #@cur_val 本字段已有的值
    def dfs(self, index, cur_val, part_ret, s):
        if index == len(s):      #结束条件
            if cur_val == 0:
                if len(part_ret) == 4:
                    self.ret.append('.'.join(str(val) for val in part_ret))
            return    
    
        if len(part_ret) >= 4:
            return
        
        cur_val = cur_val * 10 + int(s[index])
        if cur_val > 255:
            return
        
        # 当前字符作为结尾字符
        part_ret.append(cur_val)
        self.dfs(index + 1, 0, part_ret, s)
        part_ret.pop()
        
        # 当前字符加上前面的字符作为当前字段的prefix
        if cur_val != 0:
            self.dfs(index + 1, cur_val, part_ret, s)

思路2

1. dfs每个字段
2. 结束条件：到达结尾，如果字段的数目为4，则加入到结果中
3. dfs过程：从当前字符开始，找到符合条件的几个连续字符组成字段，加入到部分结果中，从字段的下一个位置继续dfs

class Solution(object):
    def restoreIpAddresses(self, s):
        """
        :type s: str
        :rtype: List[str]
        """
        self.ret = []
        self.dfs(0, [], s)
        return self.ret
    
    def dfs(self, index, part_ret, s):
        if index == len(s):
            if len(part_ret) == 4:
                self.ret.append('.'.join(str(val) for val in part_ret))
            return
        
        if len(part_ret) >= 4:
            return         
        
        cur_val = 0
        for i in range(3):
            if index + i >= len(s):
                return
            cur_val = cur_val * 10 + int(s[index + i])
            if cur_val > 255:
                return
            part_ret.append(cur_val)
            self.dfs(index + i + 1, part_ret, s)
            part_ret.pop()
            
            if cur_val == 0:
                return

总结

1. 总体来说，根据字段进行dfs的方法要考虑的情况更少，代码更简单，运行也更快，因为是作为一个整体去把握整个问题，把无效的情况尽量减少了。根据字符进行的dfs类似于状态机，思路好想，但是需要考虑的边界情况也更多
2. 注意当字段数超过4的时候停止dfs
3. 注意访问s的index不能超过s的长度