a*u
2 楼
难
★ 发自iPhone App: ChineseWeb 7.8
【在 f*******y 的大作中提到】
: 给定N个字符串，生成一个最小长度的字符串X，使的N个字符串全是X的子串
: 比如
: 123
: 234
: 答案就是1234
: 12
: 21
: 11
: 12
: 答案就是
★ 发自iPhone App: ChineseWeb 7.8
【在 f*******y 的大作中提到】
: 给定N个字符串，生成一个最小长度的字符串X，使的N个字符串全是X的子串
: 比如
: 123
: 234
: 答案就是1234
: 12
: 21
: 11
: 12
: 答案就是
f*y
3 楼
怎么做，完全不会
【在 a*****u 的大作中提到】
: 难
:
: ★ 发自iPhone App: ChineseWeb 7.8
【在 a*****u 的大作中提到】
: 难
:
: ★ 发自iPhone App: ChineseWeb 7.8
j*g
4 楼
这个答案难道不是 1121 ?
【在 f*******y 的大作中提到】
: 给定N个字符串，生成一个最小长度的字符串X，使的N个字符串全是X的子串
: 比如
: 123
: 234
: 答案就是1234
: 12
: 21
: 11
: 12
: 答案就是
f*y
5 楼
啊，对，看来人脑做是不太靠谱
【在 j****g 的大作中提到】
:
: 这个答案难道不是 1121 ?
【在 j****g 的大作中提到】
:
: 这个答案难道不是 1121 ?
s*s
6 楼
N个字符串是相同长度？
产生一个有向图，每个节点代表一个数字，比如12
(n1, n2)是个有向边 iff n1去掉第一个字符是n2的前缀。
计算欧拉路径，就可以生成最小串了。
大牛看看我的想法靠谱不？
【在 f*******y 的大作中提到】
: 给定N个字符串，生成一个最小长度的字符串X，使的N个字符串全是X的子串
: 比如
: 123
: 234
: 答案就是1234
: 12
: 21
: 11
: 12
: 答案就是
产生一个有向图，每个节点代表一个数字，比如12
(n1, n2)是个有向边 iff n1去掉第一个字符是n2的前缀。
计算欧拉路径，就可以生成最小串了。
大牛看看我的想法靠谱不？
【在 f*******y 的大作中提到】
: 给定N个字符串，生成一个最小长度的字符串X，使的N个字符串全是X的子串
: 比如
: 123
: 234
: 答案就是1234
: 12
: 21
: 11
: 12
: 答案就是
l*i
7 楼
you want hamitonian path, not eulerian path, shortest superstring is NP-hard
a*m
8 楼
难。。。。
b*e
9 楼
这个等价于旅行商问题(travelling salesman problem)。NP完全问题，多项式时间内
误解。
【在 f*******y 的大作中提到】
: 给定N个字符串，生成一个最小长度的字符串X，使的N个字符串全是X的子串
: 比如
: 123
: 234
: 答案就是1234
: 12
: 21
: 11
: 12
: 答案就是
误解。
【在 f*******y 的大作中提到】
: 给定N个字符串，生成一个最小长度的字符串X，使的N个字符串全是X的子串
: 比如
: 123
: 234
: 答案就是1234
: 12
: 21
: 11
: 12
: 答案就是
a*m
10 楼
旅行商是np hard
【在 b***e 的大作中提到】
: 这个等价于旅行商问题(travelling salesman problem)。NP完全问题，多项式时间内
: 误解。
【在 b***e 的大作中提到】
: 这个等价于旅行商问题(travelling salesman problem)。NP完全问题，多项式时间内
: 误解。
相关阅读
请教公司内换title能要求多涨点工资吗？T不幸被裁的都拿了多少遣散费啊？lc的题目质量越来越差了吧什么样的老中老板是可以跟的博后转CS 刷题还是project 真诚求建议甲骨文在Minnesota的site怎么样？swjter今天火了啊Tesla CEO 牛掰湾区混startup，注意backdoor background check ...Proveit Core Java Test想回国了要找工作了，该从啥地方入手呢？new grad诚心求比较Oracle Dev vs Google SETI(SET)面经加求建议国女在IT确实混的比国男强国内码农太苦逼了，现在流行996 (转载)滴滴打车获上海专车拍照，对Uber是利好吧【南湾】Milpitas主街1b1b出租 $1100mit上怎么这么多工作特别勤苦的人，感觉跟奴隶没什么区别了 (转载)为什么recruiter把12月份的offer推到1月