j********r
发帖数: 127 | 1 给一个string, 可以删除任意字符，求所有可以得到的palidrome字串集
我就想了个递归, 还是没有区分掉一些重复的情况，worst case O(2^n)基本同暴力解
Map> allSubSet = new HashMap();
Set getAllPalidrome(String s, int x, int y){
int ind = x * s.length() + y;
if(allSubSet.constainsKey(ind)) return allSubSet.get(ind);
Set ret = new HashSet();
if (s == null || s.size() == 0) { ret.add(""); return ret;}
if (s.size() == 1) { ret.add(s); return ret;}
for(int i = x; i <= y; i++){
for (int j = y; j >= i; j--){
if (s.charAt(i) == s.charAt(j)){
Set subSet = getAllPalidrome(s, i + 1, j - 1);
ret.addAll(subSet);
for (String str : subSet) ret.add(s.charAt(i) + str + s.charAt(i));
}
}
}
allSubSet.put(ind, ret);
return ret;
} |
l******s
发帖数: 3045 | 2 如果s不是空的话，感觉这步永远走不到
if (s == null || s.size() == 0) { ret.add(""); return ret;} |
f*******b
发帖数: 520 | 3 谢谢分享，这是leetcode原题啊哥们，用dp做，时间O(n^2) 空间O(n^2) |
f********y
发帖数: 156 | 4 要求所有可能，不是总数。这个必须dfs，怎么去重应该有些优化的地方
谢谢分享，这是leetcode原题啊哥们，用dp做，时间O(n^2) 空间O(n^2)
【在 f*******b 的大作中提到】
: 谢谢分享，这是leetcode原题啊哥们，用dp做，时间O(n^2) 空间O(n^2)
|
j********r
发帖数: 127 | 5 这个吗？
266 Palindrome Permutation
收费题。。。没钱做
【在 f*******b 的大作中提到】
: 谢谢分享，这是leetcode原题啊哥们，用dp做，时间O(n^2) 空间O(n^2)
|
l******s
发帖数: 3045 | 6 Tested on Coderpad. Looks good.
private static ISet getPal(string s){
IDictionary> dict = new Dictionary>();
for(int i = 0; i < s.Length; i++){
if(!dict.ContainsKey(s[i])) dict[s[i]] = new List();
dict[s[i]].Add(i);
}
ISet result = new HashSet();
dfs(result, new StringBuilder(), new StringBuilder(), s, 0, s.Length - 1,
dict);
return result;
}
private static void dfs(ISet result, StringBuilder sLeft,
StringBuilder sRight, string s, int left, int right, IDictionary
> dict){
for(int i = left; i <= right; i++){
result.Add(sLeft.ToString() + s[i] + sRight.ToString());
for(int j = 0; j < dict[s[i]].Count; j++)
if(dict[s[i]][j] <= i) continue;
else if (dict[s[i]][j] > right) break;
else{
sLeft.Append(s[i]);
sRight.Insert(0, s[i]);
result.Add(sLeft.ToString() + sRight.ToString());
dfs(result, sLeft, sRight, s, i + 1, dict[s[i]][j] - 1, dict);
sLeft.Length -= 1;
sRight.Remove(0, 1);
dfs(result, sLeft, sRight, s, i + 1, dict[s[i]][j] - 1, dict);
}
}
} |
j********r
发帖数: 127 | 7 这个复杂度多少？worst case好像也有o(2^n), 而且也没有很好的去重，都是用set去
重的
,
【在 l******s 的大作中提到】
: Tested on Coderpad. Looks good.
: private static ISet getPal(string s){
: IDictionary> dict = new Dictionary>();
: for(int i = 0; i < s.Length; i++){
: if(!dict.ContainsKey(s[i])) dict[s[i]] = new List();
: dict[s[i]].Add(i);
: }
: ISet result = new HashSet();
: dfs(result, new StringBuilder(), new StringBuilder(), s, 0, s.Length - 1,
: dict);
|
l******s
发帖数: 3045 | 8 好像很难。比如说这个例子abcbabcba，当找到前面一段abcba后，后面的abcba怎么也无
法预料，我无法从现有的字符串中找出这两段的关联的必然联系，所以也必须走到
Substring from index 3 to 7才能确定是不是重复，而找到那一步后的HashSet.Add
却是O(1)的，加不加没有时间上的区别。
期待更好的答案。
【在 j********r 的大作中提到】
: 这个复杂度多少？worst case好像也有o(2^n), 而且也没有很好的去重，都是用set去
: 重的
:
: ,
|
l******s
发帖数: 3045 | 9 我也没钱做，不过应该跟266和267也不同。
如果是说DP，我只想到Palindrome Patition，那就更差得远了。
【在 j********r 的大作中提到】
: 这个吗？
: 266 Palindrome Permutation
: 收费题。。。没钱做
|
l******a
发帖数: 205 | 10 求出所有可能的回文子序列，为什么会是动态规划呢？比如aaaaaaaaaa，我看符合条件
的子序列有指数级别个
【在 f*******b 的大作中提到】
: 谢谢分享，这是leetcode原题啊哥们，用dp做，时间O(n^2) 空间O(n^2)
|
|
|
w****k
发帖数: 755 | 11 不大可能，那两道收费的分别是Easy和Medium，成功率很高，这题应该不是这个级别的。
【在 f*******b 的大作中提到】
: 谢谢分享，这是leetcode原题啊哥们，用dp做，时间O(n^2) 空间O(n^2)
|
d******v
发帖数: 801 | 12 现在是刷题去找一份几十万美刀的工作啊，这百八十块的前期投资还是要舍得的，少去
两次馆子就出来了。
【在 j********r 的大作中提到】
: 这个吗？
: 266 Palindrome Permutation
: 收费题。。。没钱做
|
j********r
发帖数: 127 | 13 说的对，不过最近leetcode狂加了50道题，做不过来，而且收费的题目做的人少，答案
也少，所以我就没看。做完lintcode可以考虑再来做做这些题目。
另外我感觉题目不一定做很多，但一定要做精，做通，leetcode现在那些题，我也不能
都保证20分钟bug free用两种以上方法写出来，好几次onsite都是原题，但是因为细节
问题，都是坑坑巴巴弄了好长时间，根本没机会做follow up. 白板的时候，如果一点
细节没考虑到，想要查错，手动过test case，简直就是自虐
现在onsite好多时候，难度不在思路，在于细节了
【在 d******v 的大作中提到】
: 现在是刷题去找一份几十万美刀的工作啊，这百八十块的前期投资还是要舍得的，少去
: 两次馆子就出来了。
|
E******g
发帖数: 204 | |
w*******g
发帖数: 9932 | 15 just printing the results takes exponential time in worst case. how can it
be quadratic time.
I agree that dynamic programming is the approach
find results for size 2,4,6,... is sufficient
【在 f*******b 的大作中提到】
: 谢谢分享，这是leetcode原题啊哥们，用dp做，时间O(n^2) 空间O(n^2)
|
b***e
发帖数: 1419 | 16 /*
Find all substring palindomes. No dupe.
Vanilla JS. Run it with node.js or in browser console.
*/
function reverse(s) {
var o = '';
for (var i = s.length - 1; i >= 0; i--)
o += s[i];
return o;
};
var p = function(s) {
var prevLookup = {};
var nextLookup = {};
for (var i = 0; i < s.length; i++) {
var c = s.charAt(i);
if (!prevLookup[c]) {
prevLookup[c] = [];
nextLookup[c] = [];
}
}
for (var i = 0; i < s.length; i++) {
for(var c in prevLookup) {
var lookup = prevLookup[c];
if (c == s.charAt(i)) {
lookup[i] = i;
} else {
if (i == 0) {
lookup[i] = null;
} else {
lookup[i] = lookup[i-1];
}
}
}
}
for (var i = s.length-1; i >= 0; i--) {
for(var c in nextLookup) {
var lookup = nextLookup[c];
if (c == s.charAt(i)) {
lookup[i] = i;
} else {
if (i == s.length-1) {
lookup[i] = null;
} else {
lookup[i] = lookup[i+1];
}
}
}
}
console.log(prevLookup);
console.log(nextLookup);
var _rec = function(left, right, accum) {
console.log(accum + reverse(accum));
if (left > right) return;
for (var c in prevLookup) {
var leftMostPos = nextLookup[c][left];
var rightMostPos = prevLookup[c][right];
if (leftMostPos != null && leftMostPos <= right) {
console.log(accum + c + reverse(accum));
if (rightMostPos > leftMostPos) {
_rec(leftMostPos + 1, rightMostPos -1, accum + c);
}
}
}
};
_rec(0, s.length-1, "");
};
var s = "abcbabcba";
var s2 = "aaaaaaaa";
p(s2);
【在 j********r 的大作中提到】
: 给一个string, 可以删除任意字符，求所有可以得到的palidrome字串集
: 我就想了个递归, 还是没有区分掉一些重复的情况，worst case O(2^n)基本同暴力解
: Map> allSubSet = new HashMap();
: Set getAllPalidrome(String s, int x, int y){
: int ind = x * s.length() + y;
: if(allSubSet.constainsKey(ind)) return allSubSet.get(ind);
: Set ret = new HashSet();
: if (s == null || s.size() == 0) { ret.add(""); return ret;}
: if (s.size() == 1) { ret.add(s); return ret;}
: for(int i = x; i <= y; i++){
|
l*n
发帖数: 529 | 17 re这个，题确实不在多而在精。碰到原题要能从细节上防御好，不是原题也要践行自己
练题时的全方位考虑。
【在 j********r 的大作中提到】
: 说的对，不过最近leetcode狂加了50道题，做不过来，而且收费的题目做的人少，答案
: 也少，所以我就没看。做完lintcode可以考虑再来做做这些题目。
: 另外我感觉题目不一定做很多，但一定要做精，做通，leetcode现在那些题，我也不能
: 都保证20分钟bug free用两种以上方法写出来，好几次onsite都是原题，但是因为细节
: 问题，都是坑坑巴巴弄了好长时间，根本没机会做follow up. 白板的时候，如果一点
: 细节没考虑到，想要查错，手动过test case，简直就是自虐
: 现在onsite好多时候，难度不在思路，在于细节了
|
l*n
发帖数: 529 | 18 假设"可以删除任意字符"是能删除任意位置、任意多个，那么复杂度肯定是至少O(2^n)
。既然已经指数级别了，也不少一个O(n)，索性就直接枚举然后O(n)判断是否符合
palidrome好了。
【在 j********r 的大作中提到】
: 给一个string, 可以删除任意字符，求所有可以得到的palidrome字串集
: 我就想了个递归, 还是没有区分掉一些重复的情况，worst case O(2^n)基本同暴力解
: Map> allSubSet = new HashMap();
: Set getAllPalidrome(String s, int x, int y){
: int ind = x * s.length() + y;
: if(allSubSet.constainsKey(ind)) return allSubSet.get(ind);
: Set ret = new HashSet();
: if (s == null || s.size() == 0) { ret.add(""); return ret;}
: if (s.size() == 1) { ret.add(s); return ret;}
: for(int i = x; i <= y; i++){
|
j********r
发帖数: 127 | 19 谢谢，不过js看不太懂，能说一下思路和复杂度吗？
【在 b***e 的大作中提到】
: /*
: Find all substring palindomes. No dupe.
: Vanilla JS. Run it with node.js or in browser console.
: */
: function reverse(s) {
: var o = '';
: for (var i = s.length - 1; i >= 0; i--)
: o += s[i];
: return o;
: };
|
b***e
发帖数: 1419 | 20 看这段就够了：
// start code
var _rec = function(left, right, accum) {
console.log(accum + reverse(accum));
if (left > right) return;
for (var c in prevLookup) {
var leftMostPos = nextLookup[c][left];
var rightMostPos = prevLookup[c][right];
if (leftMostPos != null && leftMostPos <= right) {
console.log(accum + c + reverse(accum));
if (rightMostPos > leftMostPos) {
_rec(leftMostPos + 1, rightMostPos -1, accum + c);
}
}
}
};
// end code
nextLookup[c][i] = min(j, where j >= i and s[j] = c)
prevLookup[c][i] = max(k, where k <= i and s[k] = c)
【在 j********r 的大作中提到】
: 谢谢，不过js看不太懂，能说一下思路和复杂度吗？
|
|
|
j********r
发帖数: 127 | 21 感觉还是O(2^n)级别的，特别是bbbbbb, 这个要输出2^6个结果
【在 b***e 的大作中提到】
: /*
: Find all substring palindomes. No dupe.
: Vanilla JS. Run it with node.js or in browser console.
: */
: function reverse(s) {
: var o = '';
: for (var i = s.length - 1; i >= 0; i--)
: o += s[i];
: return o;
: };
|
j*****g
发帖数: 454 | 22 可以删除任意字符，那不是等价于 找所有可能序列
【在 j********r 的大作中提到】
: 给一个string, 可以删除任意字符，求所有可以得到的palidrome字串集
: 我就想了个递归, 还是没有区分掉一些重复的情况，worst case O(2^n)基本同暴力解
: Map> allSubSet = new HashMap();
: Set getAllPalidrome(String s, int x, int y){
: int ind = x * s.length() + y;
: if(allSubSet.constainsKey(ind)) return allSubSet.get(ind);
: Set ret = new HashSet();
: if (s == null || s.size() == 0) { ret.add(""); return ret;}
: if (s.size() == 1) { ret.add(s); return ret;}
: for(int i = x; i <= y; i++){
|
b***e
发帖数: 1419 | 23 Did you even bother to run the code? It's simple: copy and paste the code to
chrome console.
【在 j********r 的大作中提到】
: 感觉还是O(2^n)级别的，特别是bbbbbb, 这个要输出2^6个结果
|
s**x
发帖数: 7506 | 24 这个很找最长回文子序列差不多吧？从任意位置往两边扩。O(N^2） |
j********r
发帖数: 127 | 25 不好意思，确实不熟悉js。
刚才跑了一下，几种情况都解决的很好，很赞。
to
【在 b***e 的大作中提到】
: Did you even bother to run the code? It's simple: copy and paste the code to
: chrome console.
|
b***e
发帖数: 1419 | 26 其实不必纠结于JS。这种纯算法的题用什么都一样。这也是为什么一般interview都让
你随便挑语言。这个JS program其实跟Java program也没有什么本质区别，除了一些
language primitives不完全一样。
我的解法，如果你看懂了，是完美解法。无重复的逐一完全遍历所有的substring
palindrome。复杂度就是O(the number of palindrome substrings).
【在 j********r 的大作中提到】
: 不好意思，确实不熟悉js。
: 刚才跑了一下，几种情况都解决的很好，很赞。
:
: to
|
O****A
发帖数: 5 | 27 本题应该不是dp。Otherwise， what's the sub-optimal structure and overlapping?
blaze 的解法很巧妙。关键是建立两个不同方向的lookup table,每个entry分别是字符
以及一个数组，数组中的 i 元素 是从 i 位置往左（右）看能看到的该字符的最近位
置。然后从两边向中间扫描。
关于leetcode 266， 267 参考：
http://buttercola.blogspot.com/2015/08/leetcode-palindrome-perm |
a***u
发帖数: 383 | 28 看了半小时才看懂，这方法太帅了！
【在 b***e 的大作中提到】
: /*
: Find all substring palindomes. No dupe.
: Vanilla JS. Run it with node.js or in browser console.
: */
: function reverse(s) {
: var o = '';
: for (var i = s.length - 1; i >= 0; i--)
: o += s[i];
: return o;
: };
|
r*******g
发帖数: 1335 | 29 very nice solution
关键是对每个可能的char，维护了一维数组，数组中的i意思是从这个i看过去下一个
same char出现的位置，这样DFS就是对char来做遍历。
收藏了，准备有时间谢谢。
thanks
【在 b***e 的大作中提到】
: /*
: Find all substring palindomes. No dupe.
: Vanilla JS. Run it with node.js or in browser console.
: */
: function reverse(s) {
: var o = '';
: for (var i = s.length - 1; i >= 0; i--)
: o += s[i];
: return o;
: };
|
r*******g
发帖数: 1335 | 30 而且这个解法很巧妙的解决了奇数长和偶数长的问题。 |
|
|
r*******g
发帖数: 1335 | 31 而且这个解法很巧妙的解决了奇数长和偶数长的问题。 |
j********r
发帖数: 127 | 32 给一个string, 可以删除任意字符，求所有可以得到的palidrome字串集
我就想了个递归, 还是没有区分掉一些重复的情况，worst case O(2^n)基本同暴力解
Map> allSubSet = new HashMap();
Set getAllPalidrome(String s, int x, int y){
int ind = x * s.length() + y;
if(allSubSet.constainsKey(ind)) return allSubSet.get(ind);
Set ret = new HashSet();
if (s == null || s.size() == 0) { ret.add(""); return ret;}
if (s.size() == 1) { ret.add(s); return ret;}
for(int i = x; i <= y; i++){
for (int j = y; j >= i; j--){
if (s.charAt(i) == s.charAt(j)){
Set subSet = getAllPalidrome(s, i + 1, j - 1);
ret.addAll(subSet);
for (String str : subSet) ret.add(s.charAt(i) + str + s.charAt(i));
}
}
}
allSubSet.put(ind, ret);
return ret;
} |
l******s
发帖数: 3045 | 33 如果s不是空的话，感觉这步永远走不到
if (s == null || s.size() == 0) { ret.add(""); return ret;} |
f*******b
发帖数: 520 | 34 谢谢分享，这是leetcode原题啊哥们，用dp做，时间O(n^2) 空间O(n^2) |
f********y
发帖数: 156 | 35 要求所有可能，不是总数。这个必须dfs，怎么去重应该有些优化的地方
谢谢分享，这是leetcode原题啊哥们，用dp做，时间O(n^2) 空间O(n^2)
【在 f*******b 的大作中提到】
: 谢谢分享，这是leetcode原题啊哥们，用dp做，时间O(n^2) 空间O(n^2)
|
j********r
发帖数: 127 | 36 这个吗？
266 Palindrome Permutation
收费题。。。没钱做
【在 f*******b 的大作中提到】
: 谢谢分享，这是leetcode原题啊哥们，用dp做，时间O(n^2) 空间O(n^2)
|
l******s
发帖数: 3045 | 37 Tested on Coderpad. Looks good.
private static ISet getPal(string s){
IDictionary> dict = new Dictionary>();
for(int i = 0; i < s.Length; i++){
if(!dict.ContainsKey(s[i])) dict[s[i]] = new List();
dict[s[i]].Add(i);
}
ISet result = new HashSet();
dfs(result, new StringBuilder(), new StringBuilder(), s, 0, s.Length - 1,
dict);
return result;
}
private static void dfs(ISet result, StringBuilder sLeft,
StringBuilder sRight, string s, int left, int right, IDictionary
> dict){
for(int i = left; i <= right; i++){
result.Add(sLeft.ToString() + s[i] + sRight.ToString());
for(int j = 0; j < dict[s[i]].Count; j++)
if(dict[s[i]][j] <= i) continue;
else if (dict[s[i]][j] > right) break;
else{
sLeft.Append(s[i]);
sRight.Insert(0, s[i]);
result.Add(sLeft.ToString() + sRight.ToString());
dfs(result, sLeft, sRight, s, i + 1, dict[s[i]][j] - 1, dict);
sLeft.Length -= 1;
sRight.Remove(0, 1);
dfs(result, sLeft, sRight, s, i + 1, dict[s[i]][j] - 1, dict);
}
}
} |
j********r
发帖数: 127 | 38 这个复杂度多少？worst case好像也有o(2^n), 而且也没有很好的去重，都是用set去
重的
,
【在 l******s 的大作中提到】
: Tested on Coderpad. Looks good.
: private static ISet getPal(string s){
: IDictionary> dict = new Dictionary>();
: for(int i = 0; i < s.Length; i++){
: if(!dict.ContainsKey(s[i])) dict[s[i]] = new List();
: dict[s[i]].Add(i);
: }
: ISet result = new HashSet();
: dfs(result, new StringBuilder(), new StringBuilder(), s, 0, s.Length - 1,
: dict);
|
l******s
发帖数: 3045 | 39 好像很难。比如说这个例子abcbabcba，当找到前面一段abcba后，后面的abcba怎么也无
法预料，我无法从现有的字符串中找出这两段的关联的必然联系，所以也必须走到
Substring from index 3 to 7才能确定是不是重复，而找到那一步后的HashSet.Add
却是O(1)的，加不加没有时间上的区别。
期待更好的答案。
【在 j********r 的大作中提到】
: 这个复杂度多少？worst case好像也有o(2^n), 而且也没有很好的去重，都是用set去
: 重的
:
: ,
|
l******s
发帖数: 3045 | 40 我也没钱做，不过应该跟266和267也不同。
如果是说DP，我只想到Palindrome Patition，那就更差得远了。
【在 j********r 的大作中提到】
: 这个吗？
: 266 Palindrome Permutation
: 收费题。。。没钱做
|
|
|
l******a
发帖数: 205 | 41 求出所有可能的回文子序列，为什么会是动态规划呢？比如aaaaaaaaaa，我看符合条件
的子序列有指数级别个
【在 f*******b 的大作中提到】
: 谢谢分享，这是leetcode原题啊哥们，用dp做，时间O(n^2) 空间O(n^2)
|
w****k
发帖数: 755 | 42 不大可能，那两道收费的分别是Easy和Medium，成功率很高，这题应该不是这个级别的。
【在 f*******b 的大作中提到】
: 谢谢分享，这是leetcode原题啊哥们，用dp做，时间O(n^2) 空间O(n^2)
|
d******v
发帖数: 801 | 43 现在是刷题去找一份几十万美刀的工作啊，这百八十块的前期投资还是要舍得的，少去
两次馆子就出来了。
【在 j********r 的大作中提到】
: 这个吗？
: 266 Palindrome Permutation
: 收费题。。。没钱做
|
j********r
发帖数: 127 | 44 说的对，不过最近leetcode狂加了50道题，做不过来，而且收费的题目做的人少，答案
也少，所以我就没看。做完lintcode可以考虑再来做做这些题目。
另外我感觉题目不一定做很多，但一定要做精，做通，leetcode现在那些题，我也不能
都保证20分钟bug free用两种以上方法写出来，好几次onsite都是原题，但是因为细节
问题，都是坑坑巴巴弄了好长时间，根本没机会做follow up. 白板的时候，如果一点
细节没考虑到，想要查错，手动过test case，简直就是自虐
现在onsite好多时候，难度不在思路，在于细节了
【在 d******v 的大作中提到】
: 现在是刷题去找一份几十万美刀的工作啊，这百八十块的前期投资还是要舍得的，少去
: 两次馆子就出来了。
|
E******g
发帖数: 204 | |
w*******g
发帖数: 9932 | 46 just printing the results takes exponential time in worst case. how can it
be quadratic time.
I agree that dynamic programming is the approach
find results for size 2,4,6,... is sufficient
【在 f*******b 的大作中提到】
: 谢谢分享，这是leetcode原题啊哥们，用dp做，时间O(n^2) 空间O(n^2)
|
b***e
发帖数: 1419 | 47 /*
Find all substring palindomes. No dupe.
Vanilla JS. Run it with node.js or in browser console.
*/
function reverse(s) {
var o = '';
for (var i = s.length - 1; i >= 0; i--)
o += s[i];
return o;
};
var p = function(s) {
var prevLookup = {};
var nextLookup = {};
for (var i = 0; i < s.length; i++) {
var c = s.charAt(i);
if (!prevLookup[c]) {
prevLookup[c] = [];
nextLookup[c] = [];
}
}
for (var i = 0; i < s.length; i++) {
for(var c in prevLookup) {
var lookup = prevLookup[c];
if (c == s.charAt(i)) {
lookup[i] = i;
} else {
if (i == 0) {
lookup[i] = null;
} else {
lookup[i] = lookup[i-1];
}
}
}
}
for (var i = s.length-1; i >= 0; i--) {
for(var c in nextLookup) {
var lookup = nextLookup[c];
if (c == s.charAt(i)) {
lookup[i] = i;
} else {
if (i == s.length-1) {
lookup[i] = null;
} else {
lookup[i] = lookup[i+1];
}
}
}
}
console.log(prevLookup);
console.log(nextLookup);
var _rec = function(left, right, accum) {
console.log(accum + reverse(accum));
if (left > right) return;
for (var c in prevLookup) {
var leftMostPos = nextLookup[c][left];
var rightMostPos = prevLookup[c][right];
if (leftMostPos != null && leftMostPos <= right) {
console.log(accum + c + reverse(accum));
if (rightMostPos > leftMostPos) {
_rec(leftMostPos + 1, rightMostPos -1, accum + c);
}
}
}
};
_rec(0, s.length-1, "");
};
var s = "abcbabcba";
var s2 = "aaaaaaaa";
p(s2);
【在 j********r 的大作中提到】
: 给一个string, 可以删除任意字符，求所有可以得到的palidrome字串集
: 我就想了个递归, 还是没有区分掉一些重复的情况，worst case O(2^n)基本同暴力解
: Map> allSubSet = new HashMap();
: Set getAllPalidrome(String s, int x, int y){
: int ind = x * s.length() + y;
: if(allSubSet.constainsKey(ind)) return allSubSet.get(ind);
: Set ret = new HashSet();
: if (s == null || s.size() == 0) { ret.add(""); return ret;}
: if (s.size() == 1) { ret.add(s); return ret;}
: for(int i = x; i <= y; i++){
|
l*n
发帖数: 529 | 48 re这个，题确实不在多而在精。碰到原题要能从细节上防御好，不是原题也要践行自己
练题时的全方位考虑。
【在 j********r 的大作中提到】
: 说的对，不过最近leetcode狂加了50道题，做不过来，而且收费的题目做的人少，答案
: 也少，所以我就没看。做完lintcode可以考虑再来做做这些题目。
: 另外我感觉题目不一定做很多，但一定要做精，做通，leetcode现在那些题，我也不能
: 都保证20分钟bug free用两种以上方法写出来，好几次onsite都是原题，但是因为细节
: 问题，都是坑坑巴巴弄了好长时间，根本没机会做follow up. 白板的时候，如果一点
: 细节没考虑到，想要查错，手动过test case，简直就是自虐
: 现在onsite好多时候，难度不在思路，在于细节了
|
l*n
发帖数: 529 | 49 假设"可以删除任意字符"是能删除任意位置、任意多个，那么复杂度肯定是至少O(2^n)
。既然已经指数级别了，也不少一个O(n)，索性就直接枚举然后O(n)判断是否符合
palidrome好了。
【在 j********r 的大作中提到】
: 给一个string, 可以删除任意字符，求所有可以得到的palidrome字串集
: 我就想了个递归, 还是没有区分掉一些重复的情况，worst case O(2^n)基本同暴力解
: Map> allSubSet = new HashMap();
: Set getAllPalidrome(String s, int x, int y){
: int ind = x * s.length() + y;
: if(allSubSet.constainsKey(ind)) return allSubSet.get(ind);
: Set ret = new HashSet();
: if (s == null || s.size() == 0) { ret.add(""); return ret;}
: if (s.size() == 1) { ret.add(s); return ret;}
: for(int i = x; i <= y; i++){
|
j********r
发帖数: 127 | 50 谢谢，不过js看不太懂，能说一下思路和复杂度吗？
【在 b***e 的大作中提到】
: /*
: Find all substring palindomes. No dupe.
: Vanilla JS. Run it with node.js or in browser console.
: */
: function reverse(s) {
: var o = '';
: for (var i = s.length - 1; i >= 0; i--)
: o += s[i];
: return o;
: };
|
|
|
b***e
发帖数: 1419 | 51 看这段就够了：
// start code
var _rec = function(left, right, accum) {
console.log(accum + reverse(accum));
if (left > right) return;
for (var c in prevLookup) {
var leftMostPos = nextLookup[c][left];
var rightMostPos = prevLookup[c][right];
if (leftMostPos != null && leftMostPos <= right) {
console.log(accum + c + reverse(accum));
if (rightMostPos > leftMostPos) {
_rec(leftMostPos + 1, rightMostPos -1, accum + c);
}
}
}
};
// end code
nextLookup[c][i] = min(j, where j >= i and s[j] = c)
prevLookup[c][i] = max(k, where k <= i and s[k] = c)
【在 j********r 的大作中提到】
: 谢谢，不过js看不太懂，能说一下思路和复杂度吗？
|
j********r
发帖数: 127 | 52 感觉还是O(2^n)级别的，特别是bbbbbb, 这个要输出2^6个结果
【在 b***e 的大作中提到】
: /*
: Find all substring palindomes. No dupe.
: Vanilla JS. Run it with node.js or in browser console.
: */
: function reverse(s) {
: var o = '';
: for (var i = s.length - 1; i >= 0; i--)
: o += s[i];
: return o;
: };
|
j*****g
发帖数: 454 | 53 可以删除任意字符，那不是等价于 找所有可能序列
【在 j********r 的大作中提到】
: 给一个string, 可以删除任意字符，求所有可以得到的palidrome字串集
: 我就想了个递归, 还是没有区分掉一些重复的情况，worst case O(2^n)基本同暴力解
: Map> allSubSet = new HashMap();
: Set getAllPalidrome(String s, int x, int y){
: int ind = x * s.length() + y;
: if(allSubSet.constainsKey(ind)) return allSubSet.get(ind);
: Set ret = new HashSet();
: if (s == null || s.size() == 0) { ret.add(""); return ret;}
: if (s.size() == 1) { ret.add(s); return ret;}
: for(int i = x; i <= y; i++){
|
b***e
发帖数: 1419 | 54 Did you even bother to run the code? It's simple: copy and paste the code to
chrome console.
【在 j********r 的大作中提到】
: 感觉还是O(2^n)级别的，特别是bbbbbb, 这个要输出2^6个结果
|
s**x
发帖数: 7506 | 55 这个很找最长回文子序列差不多吧？从任意位置往两边扩。O(N^2） |
j********r
发帖数: 127 | 56 不好意思，确实不熟悉js。
刚才跑了一下，几种情况都解决的很好，很赞。
to
【在 b***e 的大作中提到】
: Did you even bother to run the code? It's simple: copy and paste the code to
: chrome console.
|
b***e
发帖数: 1419 | 57 其实不必纠结于JS。这种纯算法的题用什么都一样。这也是为什么一般interview都让
你随便挑语言。这个JS program其实跟Java program也没有什么本质区别，除了一些
language primitives不完全一样。
我的解法，如果你看懂了，是完美解法。无重复的逐一完全遍历所有的substring
palindrome。复杂度就是O(the number of palindrome substrings).
【在 j********r 的大作中提到】
: 不好意思，确实不熟悉js。
: 刚才跑了一下，几种情况都解决的很好，很赞。
:
: to
|
O****A
发帖数: 5 | 58 本题应该不是dp。Otherwise， what's the sub-optimal structure and overlapping?
blaze 的解法很巧妙。关键是建立两个不同方向的lookup table,每个entry分别是字符
以及一个数组，数组中的 i 元素 是从 i 位置往左（右）看能看到的该字符的最近位
置。然后从两边向中间扫描。
关于leetcode 266， 267 参考：
http://buttercola.blogspot.com/2015/08/leetcode-palindrome-perm |
a***u
发帖数: 383 | 59 看了半小时才看懂，这方法太帅了！
【在 b***e 的大作中提到】
: /*
: Find all substring palindomes. No dupe.
: Vanilla JS. Run it with node.js or in browser console.
: */
: function reverse(s) {
: var o = '';
: for (var i = s.length - 1; i >= 0; i--)
: o += s[i];
: return o;
: };
|
r*******g
发帖数: 1335 | 60 very nice solution
关键是对每个可能的char，维护了一维数组，数组中的i意思是从这个i看过去下一个
same char出现的位置，这样DFS就是对char来做遍历。
收藏了，准备有时间谢谢。
thanks
【在 b***e 的大作中提到】
: /*
: Find all substring palindomes. No dupe.
: Vanilla JS. Run it with node.js or in browser console.
: */
: function reverse(s) {
: var o = '';
: for (var i = s.length - 1; i >= 0; i--)
: o += s[i];
: return o;
: };
|
|
|
r*******g
发帖数: 1335 | 61 而且这个解法很巧妙的解决了奇数长和偶数长的问题。 |
r*******g
发帖数: 1335 | 62 而且这个解法很巧妙的解决了奇数长和偶数长的问题。 |
k****r
发帖数: 807 | 63 anyone who can share a java/c++ code? Thank you and Blaze! |
I******c
发帖数: 163 | 64 我的java实现，参考了Blaze的思路，不过不知道真正理解了他的思路没有，因为我不
太看得懂javascript.下面是几个点：
1. 这个题目用的是backtracking而不是dp，因为dp不可能给你产生排列组合。dp通常
就是给你一个最值。
2. 时间复杂度是指数级。
3. 题目的本质是产生排列。
4. 一般的backtracking来形成字符串的话,从现有字母集中每次任意挑一个字母,然后
从剩下的字母里继续挑。把所有字母都加到字符串里面去了，这轮程序也就完了。这个
题目因为有个顺序的限制条件，决定程序怎样进行下去并不能用剩下多少字符来决定，
而应该是用已经加入字符串的字母的位置来决定。
import java.util.HashMap;
import java.util.List;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.Set;
public class Example5 {
public static void main(String [] args){
Example5 o = new Example5();
List results = o.setUp("abcbabcba");
for(String str: results){
System.out.println(str);
}
}
public List setUp(String palidrome){
HashMap > map = new HashMap
List>();
HashMap locations = new HashMap
Pointers>();
char [] chs = palidrome.toCharArray();
int i = 0;
for(i=0;i
if(map.containsKey(chs[i])){
map.get(chs[i]).add(i);
}
else{
List tmp = new ArrayList ();
tmp.add(i);
map.put(chs[i],tmp);
}
}
Set keySet = map.keySet();
Iterator iter = keySet.iterator();
List results = new ArrayList ();
while(iter.hasNext()){
Character ch=iter.next();
//results.add(ch.toString());
int size = map.get(ch).size();
locations.put(ch, new Pointers(0,size-1));
}
StringBuilder sb1 = new StringBuilder();
StringBuilder sb2 = new StringBuilder();
dfs(results,0,chs.length-1,sb1,sb2,keySet,map,locations);
return results;
}
private class Pointers {
int left;
int right;
public Pointers(int left, int right){
this.left = left;
this.right = right;
}
}
public void dfs (List results, int left, int right,
StringBuilder sb1, StringBuilder sb2, Set keySet, HashMap <
Character, List> map, HashMap locations) {
Iterator iter = keySet.iterator();
while(iter.hasNext()){
Character ch=iter.next();
//System.out.println("ch="+ch+" left="+left+" right="+right);
Pointers p=locations.get(ch);
//System.out.println("left1="+p.left+" right1="+p.right);
List nums = map.get(ch);
int oldLeft = p.left;
int oldRight = p.right;
while((p.left<=p.right)&&(nums.get(p.left)
p.left++;
}
while((p.left<=p.right)&&(nums.get(p.right)>right)){
p.right--;
}
if(p.left<=p.right){
results.add(sb1.toString()+ch+sb2.toString());
//System.out.println(sb1.toString()+ch+sb2.toString());
}
if(p.left
sb1.append(ch);
sb2.insert(0,ch);
int tmp1 = p.left;
int tmp2 = p.right;
p.left++;
p.right--;
//System.out.println(sb1.toString()+sb2.toString());
results.add(sb1.toString()+sb2.toString());
dfs(results,nums.get(tmp1)+1,nums.get(tmp2)-1,sb1,sb2,keySet
,map,locations);
sb1.deleteCharAt(sb1.length()-1);
sb2.deleteCharAt(0);
}
p.left = oldLeft;
p.right = oldRight;
}
}
} |
