这道面试题要是ONSITE - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

这道面试题要是ONSITE

这道面试题要是ONSITE# JobHunting - 待字闺中

c*a2018-04-07 07:04

1 楼

最少要20分钟才能写出最优（时间和空间复杂度）并且无虫的算法来？
=================
Given a string s, partition s such that every substring of the partition is
a palindrome.
Retur n all possible palindrome partitioning of s.
For example, given s = "aab", Retur n
[
[ " aa" , " b" ],
[ " a" , " a" , " b" ]
]

G*O2018-04-07 07:04

2 楼

20 分钟不是很正常吗？
看到回文字符串的题目，基本就是dp套路，先建立p[i][j] 表示字符串 i 到 j是不是
回文（有个很简单的算法）
然后根据题目要求在写个转移方程式就好了。。。。

is

【在 c*******a 的大作中提到】

: 最少要20分钟才能写出最优（时间和空间复杂度）并且无虫的算法来？
: =================
: Given a string s, partition s such that every substring of the partition is
: a palindrome.
: Retur n all possible palindrome partitioning of s.
: For example, given s = "aab", Retur n
: [
: [ " aa" , " b" ],
: [ " a" , " a" , " b" ]
: ]

s*x2018-04-07 07:04

3 楼

这题就暴力扫一遍就行了啊。因为要打印所有结果。
Followup 那个才需要dp.

o*r2018-04-07 07:04

4 楼

这道我记得好像做过，有可能是leetcode原题

c*y2018-04-07 07:04

5 楼

我的想法：先找到所有子回文串，O(n^2), 记录到map(start: [ends]), 然后从start=
0 开始dfs找到所有可能性，步长可从map获得，这一步的复杂度和结果的 size应该一
样。

is

【在 c*******a 的大作中提到】

G*O2018-04-07 07:04

6 楼

上代码吧，标准模板，搞出p i,j ，弄清楚回文子串有哪些，然后DFS，
public List> partition(String s) {
List> res = new ArrayList<>();
int len = s.length();
boolean[][] p = new boolean[len][len];
for (int i = 0; i < len; i++) {
p[i][i] = true;
}

for (int i = len - 1; i >= 0; i--) {
for (int j = i + 1; j < len; j++) {
if (s.charAt(j) == s.charAt(i)) {
if (p[i + 1][j - 1] || j - i < 2) {
p[i][j] = true;
}
}
}
}

dfs(s, 0, p, res, new ArrayList());
return res;
}

private void dfs(String s, int pos, boolean[][] p, List>
res, List path) {
if (pos == s.length()) {
res.add(new ArrayList(path));
return;
}
for (int i = pos; i < s.length(); i++) {
if (!p[pos][i]) continue;
path.add(s.substring(pos, i+1));
dfs(s, i+1, p, res, path);
path.remove(path.size() - 1);
}

}

start=

【在 c*******y 的大作中提到】

: 我的想法：先找到所有子回文串，O(n^2), 记录到map(start: [ends]), 然后从start=
: 0 开始dfs找到所有可能性，步长可从map获得，这一步的复杂度和结果的 size应该一
: 样。
:
: is

H*52018-04-07 07:04

7 楼

这题是Linkedin用来凑人数的耍人题，有没有面L家遇到这题还拿到offer的可以吱一声。
我目前感觉最优解是prefix树，代码400多行。

H*52018-04-07 07:04

8 楼

你这个解估计会被L的面试官鄙视，效率太低了。我有5种解法的代码，eclipse上跑长
度为1000的串这个解法比prefix 树慢N倍

: 上代码吧，标准模板，搞出p i,j ，弄清楚回文子串有哪些，然后DFS，

: public List partition(String s) {

: List res = new ArrayList();

: int len = s.length();

: boolean[][] p = new boolean[len][len];

: for (int i = 0; i

【在 G**O 的大作中提到】

: 上代码吧，标准模板，搞出p i,j ，弄清楚回文子串有哪些，然后DFS，
: public List> partition(String s) {
: List> res = new ArrayList<>();
: int len = s.length();
: boolean[][] p = new boolean[len][len];
: for (int i = 0; i < len; i++) {
: p[i][i] = true;
: }
:
: for (int i = len - 1; i >= 0; i--) {

m*52018-04-07 07:04

9 楼

dfs暴力就可以了。因为题目要所有的。

is

【在 c*******a 的大作中提到】

G*O2018-04-07 07:04

10 楼

我在某家。。。。。面试写400行干嘛。。
看看LC前几名的解法
https://leetcode.com/problems/palindrome-partitioning/discuss/

【在 H**********5 的大作中提到】

: 你这个解估计会被L的面试官鄙视，效率太低了。我有5种解法的代码，eclipse上跑长
: 度为1000的串这个解法比prefix 树慢N倍
:
:
: 上代码吧，标准模板，搞出p i,j ，弄清楚回文子串有哪些，然后DFS，
:
: public List partition(String s) {
:
: List res = new ArrayList();
:
: int len = s.length();
:
: boolean[][] p = new boolean[len][len];
:
: for (int i = 0; i