陈中正的网络日志

LeetCode: Restore IP Address

题目

https://oj.leetcode.com/problems/restore-ip-addresses/

分析

这道题和八皇后类似,采用回溯法来解决,也就是 剪枝过的DFS。

代码

class Solution
{
public:
    vector<string> restoreIpAddresses(string s)
    {
        s_ = s;
        helper("", 1, 0);

        return res_;
    }

    void helper(string ip, int segment_num, int index)
    {
        if (segment_num == 4)
        {
            string ip_segment = s_.substr(index, s_.size() - index);
            if (!ip_segment.empty() && ip_segment.length() <= 3 
                    && isValid(ip_segment))
            {
                ip += ip_segment;
                res_.push_back(ip);
            }
        }
        else
        {
            for (int i = 1; i <= 3 && i <= s_.size() - index; i++)
            {
                string ip_segment = s_.substr(index, i);
                if (isValid(ip_segment))
                    helper(ip + ip_segment + '.', segment_num + 1, index + i);
            }
        }
    }

    bool isValid(string ip_segment)
    {
        if (ip_segment[0] == '0')
            return (ip_segment == "0");
        if (stoi(ip_segment) <= 255)
            return true;
        else
            return false;
    }

private:
    string s_;
    vector<string> res_;
};

Note

  1. 一开始做的采用一种非常麻烦的方法,每一层的solution记录每个点的位置,这样一来 isValid以及最后生成IP的时候就会特别的繁琐。

简单的方法是直接在每层递归中记录一个ip_segment,这样能够省好多的代码。

  1. stoi()的参数不能为“”,也不能超出int的表示范围,否则程序会崩溃。

因此在调用stoi()之前要先检查一下参数。

  1. 像stoi()这种函数如果崩溃了,可以采用  break + display 的方法在gdb 中找出崩溃的原因。

参考

http://blog.csdn.net/u011095253/article/details/9158449

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/40989329

Categories:  OJ题解 

« JNI编程—— Linux下编写一个最简单的JNI程序 LeetCode: LRU Cache »