l*******s
发帖数: 1258 | 1 Given a string containing only digits, restore it by returning all possible
valid IP address combinations.
For example:
Given "25525511135",
return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)
做完了，也基本bug free。但是比较迷惑于复杂度。
用递归的话，这个复杂度是多少？O(n平方)?
thx！ | c***s
发帖数: 192 | 2 严格来说这道题的复杂度是 O(1).
只要大于12位的都扔掉，小于等于12位的肯定能在一个常数时间内完成。
possible
【在 l*******s 的大作中提到】
: Given a string containing only digits, restore it by returning all possible
: valid IP address combinations.
: For example:
: Given "25525511135",
: return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)
: 做完了，也基本bug free。但是比较迷惑于复杂度。
: 用递归的话，这个复杂度是多少？O(n平方)?
: thx！
| c********t
发帖数: 5706 | 3 嗯，跟我想的一样，如果ip无限长，那基本上是个 3^n的吧
【在 c***s 的大作中提到】
: 严格来说这道题的复杂度是 O(1).
: 只要大于12位的都扔掉，小于等于12位的肯定能在一个常数时间内完成。
:
: possible
| l*******s
发帖数: 1258 | 4 主要是这个玩意 每个ip的小段有个数 一共四个ip小段
暴力解的话，四个for循环，每个for循环操作3个数，复杂度就是3^4，常数啊。。。
那么递归的复杂度呢？也是3^4常数？ |
|
