找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 2492|回复: 3
收起左侧

[Google] 求问一道G家题

[复制链接]

11

主题

1

精华

357

积分

高级会员

Rank: 3Rank: 3

积分
357
发表于 12-31-2014 12:38 PM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
本帖最后由 cpcs 于 12-31-2014 12:48 PM 编辑
; K( h: @1 r2 R+ {- W8 P- _
2 s* L: [2 l( E2 S' n# _4 ]- SAbbreviation: apple can be abbreviated to 5, a4, 4e, a3e, …4 X. M$ q( f0 z0 b
    Given a target string (internationalization), and a set of strings, 8 \, E! n3 ~7 X9 ~! I/ p
return the minimal length of abbreviation of this target string so that it
1 W- @3 ?3 i. rwon’t conflict with abbrs of the strings in the set.
" _( k9 [9 Z4 ^% L- s- w
2 C6 t9 i: x. r“apple”, [“blade”] -> a4 (5 is conflicted with “blade”)0 j0 N1 V" m/ _# g2 p8 y
“apple”, [“plain”, “amber”, “blade”]  ->  ???% t& C8 b) {% W- I& T' k

0 T! H6 C. j0 G: l; i还有一道类似的2 A/ h0 }7 X# w; g8 H9 @
给一字典,求其中某单词的最短缩写。比如internationalization可以缩写为i18n而不+ e/ r  O* i) f1 f, ?* x' R
产生歧义。 举例:一字典有6个单词:9 d& }6 [* C& w+ h8 w% H
hello
" P  e$ m: g* u; |world# z7 e! A& e: E4 U
would
7 l! c+ D2 j, L# K2 jlord
& y0 n; _8 r- x- ^% ?# B" Qhell
2 g% n+ j' }, |; K  slanguage
# v- E8 d& s% u+ V& t2 [4 q依次可以缩写为 hello -> 4o or h4 world -> 2r2 would -> 2u2 lord -> l3 or 3d 5 g4 [$ i$ z' P3 _# h: Q* h6 L
hell -> 3l or h3 language -> 8
1 D( y" h3 [- o0 G+ C$ T+ n5 Y% W( w9 j
想了好久,但还是没有一个明确的思路,望大神指导一二' [/ w( N) W4 ]0 m% d; |0 E2 K
发表于 12-31-2014 12:49 PM | 显示全部楼层
见过 除了枚举 找不到好的方法
回复 支持 反对

使用道具 举报

17

主题

10

精华

340

积分

高级会员

Rank: 3Rank: 3

积分
340
发表于 12-31-2014 07:08 PM | 显示全部楼层
  1. public static void dfs(String set, int i, ArrayList<String> ret, String word){
    ) u, }. i! r: k1 z! l0 h
  2.                 if(i == word.length()){
    ; F( K  c( `/ ^. b; p9 T# e
  3.                         ret.add(set);+ P' @' ?0 K( h% F
  4.                         return;
    * {. J3 \5 O: h7 ?4 d6 P
  5.                 }
    2 w- `; x& |  t7 ?5 h
  6.                 int count = 0;+ Y) r8 P' @: T; |7 y7 F7 y) s% L
  7.                 if(set.length() == 0) {
    6 E6 q6 c( U6 a" ]
  8.                         dfs("1", i + 1, ret, word);
    6 l3 [# a/ `( C7 L3 N( s
  9.                         dfs(word.charAt(0) + "", i + 1, ret, word);5 D. \+ w5 ]' _$ E7 J. Y
  10.                 }: I# R$ s' P: H9 \4 w
  11.                 else{& u4 F0 J3 m* |+ s4 G, u9 l8 ]
  12.                         char last = set.charAt(set.length() - 1);  _9 H' L" {3 w
  13.                         if(!Character.isLetter(last)){1 Q) t6 `, V5 V. l+ n) }; V5 O
  14.                                 count = Integer.valueOf("" + last) + 1;
    1 p/ I4 ~' e. D- w
  15.                                 dfs(set.substring(0, set.length() -1) + count, i + 1, ret, word);
    + h! k( Z7 I/ T* o' S5 j' a3 ^6 B
  16.                                 dfs(set + word.charAt(i), i + 1, ret, word);
    5 x( S3 B& g5 j; ^8 e* s! U5 P
  17.                         }
    $ J8 w; s# ~2 p4 ?+ p; P
  18.                         else{
    & L9 o. U) z7 N% J1 g
  19.                                 count = 1;! c' f" g8 W! m1 |, {
  20.                                 dfs(set + count, i + 1, ret, word);
    " e! J! F" y' |+ ?5 s: ~3 D! c4 Z( z6 t
  21.                                 dfs(set + word.charAt(i), i + 1, ret, word);
    0 E1 |1 j! a5 S0 P& _
  22.                         }
    " Y7 X9 X9 {, n# g2 O; }2 c5 a
  23.                 }6 H' L" G9 b% z1 _: u& V( a
  24.                 9 f  Y2 [. U! Q/ u% [# p! Q; m
  25.         }
复制代码
6 J9 e4 u7 I7 h( e" E" z  L# T' l
补充内容 (12-31-2014 07:08 PM):
2 s  c  u4 `% }( d; o9 nret就是所有可能的解
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表