w*******1
发帖数: 32 | 1 原题在这：
https://oj.leetcode.com/problems/palindrome-partitioning/
根据结果分析猜是O(n*2^n),但是不会从代码分析。请教各位大牛，如果用以下代码，
怎么分析复杂度？
public void palindromeHelper(String input, List> resultList
, List curResult, int index){
if(index == input.length()){
resultList.add(new ArrayList(curResult));
return;
}
for(int i=index; i
String substring = input.substring(index, i+1);
if(isPalindrome(input, index, i)){
curResult.add(substring);
palindromeHelper(input, resultList, curResult, i+1);
curResult.remove(curResult.size()-1); }
}
}
call with: palindromeHelper(s, resultList, curResult, 0);
isPalindrome()代码就不附了，最简单O(n)那种。
多谢！！ | t*******y
发帖数: 22 | 2 last character will be accessed n times; last second character will be
accessed n-1 times. the complexity is n+(n-1)+(n-2)+...1=O(n^2)
since you isPalindrome takes O(n), total will be O(n^3).
if you calculate isPlaindrome first, it takes O(n^2); in your recursive
function, it will take O(1) to call that function. overall complexiy will be
O(n^2). | w*******1
发帖数: 32 | 3 多谢！！
但是从结果来看，一个长度为N的string，partition的结果个数为2^(N-1),相当于把N-
1个挡板插入N个字符里：
string: 1234
C30: 1234
C31: 1|234, 12|34, 123|4
C32: 1|2|34, 1|23|4, 12|3|4
C33: 1|2|3|4
C30 + C31 + C32 + C33 = 2^3
所以不考虑isPalindrom的影响，复杂度应该不低于O(2^N)
be
【在 t*******y 的大作中提到】
: last character will be accessed n times; last second character will be
: accessed n-1 times. the complexity is n+(n-1)+(n-2)+...1=O(n^2)
: since you isPalindrome takes O(n), total will be O(n^3).
: if you calculate isPlaindrome first, it takes O(n^2); in your recursive
: function, it will take O(1) to call that function. overall complexiy will be
: O(n^2).
| t*******y
发帖数: 22 | |
|
