l**z
发帖数: 78 | 1 给一字典,求其中某单词的最短缩写。比如internationalization可以缩写为i18n而不
产生歧义
举例：一字典有6个单词：
hello
world
would
lord
hell
language
依次可以缩写为
hello -> 4o or h4
world -> 2r2
would -> 2u2
lord -> l3 or 3d
hell -> 3l or h3
language -> 8 |
t****a
发帖数: 1212 | |
l**z
发帖数: 78 | 3 比如 world可以缩写为 2r2。即2个字母在r前，2个字母在r后。字典中满足这规则的只
有world
【在 t****a 的大作中提到】
: 看不懂。缩写的规则是什么？
|
l**z
发帖数: 78 | |
f*****e
发帖数: 2992 | 5 为什么不是
hello -> 5
world -> w4
would -> 4d
lord -> 4
hell -> h3
language -> 8
【在 l**z 的大作中提到】
: 给一字典,求其中某单词的最短缩写。比如internationalization可以缩写为i18n而不
: 产生歧义
: 举例：一字典有6个单词：
: hello
: world
: would
: lord
: hell
: language
: 依次可以缩写为
|
l**z
发帖数: 78 | 6 hello -> 5 有歧义啊。5可能是hello, world, would
【在 f*****e 的大作中提到】
: 为什么不是
: hello -> 5
: world -> w4
: would -> 4d
: lord -> 4
: hell -> h3
: language -> 8
|
t*********h
发帖数: 941 | 7 着五花八门的题越来越多了
if length is unique, output length
else:
find a diff char, output rest length?
【在 l**z 的大作中提到】
: 给一字典,求其中某单词的最短缩写。比如internationalization可以缩写为i18n而不
: 产生歧义
: 举例：一字典有6个单词：
: hello
: world
: would
: lord
: hell
: language
: 依次可以缩写为
|
l*********8
发帖数: 4642 | 8 4个单词：
ABC
ABD
ACD
ACC
你的算法如何执行？
【在 t*********h 的大作中提到】
: 着五花八门的题越来越多了
: if length is unique, output length
: else:
: find a diff char, output rest length?
|
t*********h
发帖数: 941 | 9 there's no unique char at all positions. so you cant compress them
【在 l*********8 的大作中提到】
: 4个单词：
: ABC
: ABD
: ACD
: ACC
: 你的算法如何执行？
|
l*********8
发帖数: 4642 | 10 compress results can be:
1BD
1BC
1CD
1CC
If you think this is not compression, we can use the following example:
ABCBC
ABCBD
ABCCD
ABCCC
compress results can be:
3BD
3BC
3CD
3CC
【在 t*********h 的大作中提到】
: there's no unique char at all positions. so you cant compress them
|
|
|
l**z
发帖数: 78 | 11 估一下时空复杂度呢
【在 l*********8 的大作中提到】
: compress results can be:
: 1BD
: 1BC
: 1CD
: 1CC
: If you think this is not compression, we can use the following example:
: ABCBC
: ABCBD
: ABCCD
: ABCCC
|
p*****2
发帖数: 21240 | 12 不知道应不应该先定义一下缩写的规格。
会有这种情况吗？
1a2b3cd15d
感觉可能的缩写有点不好控制了。 |
l**z
发帖数: 78 | 13 会的。求最短的缩写
【在 p*****2 的大作中提到】
: 不知道应不应该先定义一下缩写的规格。
: 会有这种情况吗？
: 1a2b3cd15d
: 感觉可能的缩写有点不好控制了。
|
f*****e
发帖数: 2992 | 14 那就只能用brutal force了，先尝试用一个character作为key，找出那些可以用一个
character identify的string，然后尝试用两个character作为key对剩下的string做类
似操作。
【在 l**z 的大作中提到】
: 会的。求最短的缩写
|
p*****2
发帖数: 21240 | 15 按长度分组，不同长度很好搞定，不会有冲突。
如果分组中只有一个，就可以直接用长度来表示了。
否则，如果某位置只是出现了一次，可以用这个位置来表示，当然第一个，最后一个字
母优先。
剩下的看两个字母不同。连续两个优先。
然后看三个字母，。。。 |
