星空网 > 软件开发 > Java

CareerCup: 17.14 minimize unrecognized characters

Oh, no! You have just completed a lengthy document when you have an unfortu-nate Find/Replace mishap. You have accidentally removed all spaces, punctuation,and capitalization in the document. A sentence like "I reset the computer. It stilldidn't boot!" would become "iresetthecomputeritstilldidntboot". You figure that youcan add back in the punctation and capitalization later, once you get the individualwords properly separated. Most of the words will be in a dictionary, but some strings,like proper names, will not.Given a dictionary (a list of words), design an algorithm to find the optimal way of"unconcatenating" a sequence of words. In this case, "optimal" is defined to be theparsing which minimizes the number of unrecognized sequences of characters.For example, the string "jesslookedjustliketimherbrother" would be optimally parsedas "JESS looked just like TIM her brother". This parsing has seven unrecognized char-acters, which we have capitalized for clarity.

这是CareerCup Chapter 17的第14题,我没怎么看CareerCup上的解法,但感觉这道题跟Word Break, Palindrome Partition II很像,都是有一个dictionary, 可以用一维DP来做,用一个int[] res = new int[len+1]; res[i] refers to minimized # of unrecognized chars in first i chars, res[0]=0, res[len]即为所求。

有了维护量,现在需要考虑转移方程,如下:

int unrecogNum = dict.contains(s.substring(j, i))? 0 : i-j; //看index从j到i-1的substring在不在dictionary里,如果不在,unrecogNum=j到i-1的char数
res[i] = Math.min(res[i], res[j]+unrecogNum);

 

亲测,我使用的case都过了,只是不知道有没有不过的Corner Case:

 1 package fib; 2  3 import java.util.Arrays; 4 import java.util.HashSet; 5 import java.util.Set; 6  7 public class unconcatenating { 8   public int optway(String s, Set<String> dict) { 9     if (s==null || s.length()==0) return 0;10     int len = s.length();11     if (dict.isEmpty()) return len;12     int[] res = new int[len+1]; // res[i] refers to minimized # of unrecognized chars in first i chars13     Arrays.fill(res, Integer.MAX_VALUE);14     res[0] = 0;15     for (int i=1; i<=len; i++) {16       for (int j=0; j<i; j++) {17         String str = s.substring(j, i);18         int unrecogNum = dict.contains(str)? 0 : i-j;19         res[i] = Math.min(res[i], res[j]+unrecogNum);20       }21     }22     return res[len];23   }24 25 26   public static void main(String[] args) {27     unconcatenating example = new unconcatenating();28     Set<String> dict = new HashSet<String>();29     dict.add("reset");30     dict.add("the");31     dict.add("computer");32     dict.add("it");33     dict.add("still");34     dict.add("didnt");35     dict.add("boot");36     int result = example.optway("johnresetthecomputeritdamnstilldidntboot", dict);37     System.out.print("opt # of unrecognized chars is ");38     System.out.println(result);39   }40 41 }

output是:opt # of unrecognized chars is 8




原标题:CareerCup: 17.14 minimize unrecognized characters

关键词:

*特别声明:以上内容来自于网络收集,著作权属原作者所有,如有侵权,请联系我们: admin#shaoqun.com (#换成@)。

牛津小马哥SEO教程第五天:如何修复死链 ?:https://www.ikjzd.com/articles/23104
亚马逊数据分析选品技巧,助力卖家选好产品!:https://www.ikjzd.com/articles/23106
你知道亚马逊店铺产品少,销量却很高的秘密吗?:https://www.ikjzd.com/articles/23108
亚马逊开店秘诀,新手快了解一下!:https://www.ikjzd.com/articles/23109
注意这几点,大大提高亚马逊申诉信成功率:https://www.ikjzd.com/articles/23113
2019年Shopee斋月大促最强选品指南:https://www.ikjzd.com/articles/23116
TikTok斥资210万美元游说美国参议院阻止法案通过 :https://www.goluckyvip.com/news/188220.html
北京飞机票查询(快速查询北京至各地机票价格和航班信息):https://www.vstour.cn/a/366178.html
相关文章
我的浏览记录
最新相关资讯
海外公司注册 | 跨境电商服务平台 | 深圳旅行社 | 东南亚物流