果洛wap网站建设多少钱,申请免费域名空间,怎样进行文化建设,怎么登录微信小程序平台题目描述#xff1a; 如果单词列表#xff08;words#xff09;中的一个单词包含牌照#xff08;licensePlate#xff09;中所有的字母#xff0c;那么我们称之为完整词。在所有完整词中#xff0c;最短的单词我们称之为最短完整词。
单词在匹配牌照中的字母时不区分大…题目描述 如果单词列表words中的一个单词包含牌照licensePlate中所有的字母那么我们称之为完整词。在所有完整词中最短的单词我们称之为最短完整词。
单词在匹配牌照中的字母时不区分大小写比如牌照中的 P 依然可以匹配单词中的 p 字母。
我们保证一定存在一个最短完整词。当有多个单词都符合最短完整词的匹配条件时取单词列表中最靠前的一个。
牌照中可能包含多个相同的字符比如说对于牌照 PP单词 pair 无法匹配但是 supper 可以匹配。 示例 1
输入licensePlate 1s3 PSt, words [step, steps, stripe, stepple]
输出steps
说明最短完整词应该包括 s、p、s 以及 t。对于 step 它只包含一个 s 所以它不符合条件。同时在匹配过程中我们忽略牌照中的大小写。 示例 2
输入licensePlate 1s3 456, words [looks, pest, stew, show]
输出pest
说明存在 3 个包含字母 s 且有着最短长度的完整词但我们返回最先出现的完整词。注意:
牌照licensePlate的长度在区域[1, 7]中。牌照licensePlate将会包含数字、空格、或者字母大写和小写。单词列表words长度在区间 [10, 1000] 中。每一个单词 words[i] 都是小写并且长度在区间 [1, 15] 中。 想法1把licensePlate中的字母挑出来存放到一个list中然后遍历words中的每一个字符串判断list中是否包含该字符若存在该字符则将该字符从list中移除。当list中为空时就说明licensePlate在words中匹配了。同时还需要设置一个min变量和result变量min用来记录当前最短字符串的长度result用来记录对应的最短字符串。
上代码
class Solution {public String shortestCompletingWord(String licensePlate, String[] words){licensePlate licensePlate.toLowerCase();ArrayListCharacter list pick(licensePlate);//用来记录最短单词长度的min和最短单词的resultint min Integer.MAX_VALUE;String result null;for (int i 0; i words.length; i) {//先将list复制一份对备份进行操作ArrayListCharacter temp (ArrayListCharacter) list.clone();int len words[i].length();for (int j 0; j len; j) {//list中含有words[i]中的字符将该字符移除//此处有一个陷阱如果是这样写的话temp.remove(words[i].charAt(j));//很可能报数组越界的错误因为list会调用这个remove(int index)方法;//自动把char类型转为int类型而我们想要的是remove(Object o)//所以应该传入的参数应该是new Character(words[i].charAt(j))if(temp.contains(words[i].charAt(j))){temp.remove(new Character(words[i].charAt(j)));}if(temp.size() 0 len min){min len;result words[i];}}}return result;}/*** 将licensePlate中的字母挑出来* 并存放到list中*/public ArrayListCharacter pick(String S){ArrayListCharacter list new ArrayList();for (int i 0; i S.length(); i) {if(S.charAt(i) a S.charAt(i) z){list.add(S.charAt(i));}}return list;}
}
上面代码中提到的坑只怪自己太菜还debug了半天。。。。。 ╮(╯▽╰)╭ 想法2同样的先把licensePlate中的字母先挑出来但是不把对应的字符记录下来而是用一个长度为26的int型数组来存放每个字母在licensePlate中出现的次数。同样在遍历words中的每一个字符串时也用一个长度为26的int型数组来存放每个字母出现的次数。然后将这两个数字进行比较第一个数组中的26个值都小于或等于第二个数组中的26个值即可。同时用一个变量index来记录当前最短字符的下标。
上代码
class Solution {public String shortestCompletingWord(String licensePlate, String[] words) {int[] count new int[26];//统计licensePlate中每个字母出现的次数for (int i 0; i licensePlate.length(); i) {String lp licensePlate.toLowerCase();char c lp.charAt(i);if (Character.isLetter(c)) {count[c - a];}}int index Integer.MAX_VALUE;//记录最短字符串的下标int k 0;for (String word : words) {int[] count2 new int[26];//统计字符串word中每个字母出现的次数for (int i 0; i word.length(); i) {char c word.charAt(i);count2[c - a];}boolean flag true;//第二个数组中只要有一个数字小于第一个数组中的值//就表明当前的word不匹配licensePlatefor (int t 0; t 26; t) {if (count[t] ! 0 count2[t] count[t]) {flag false;break;}}//更新index的值if (flag true) {if (index Integer.MAX_VALUE)index k;else if (word.length() words[index].length())index k;}k;}return words[index];}
}
以上两种方法的运行时间都差不多没有太大差别。
最后各位路过的大佬如果你有更好的方法欢迎指导谢谢哦 文章转载自： http://www.morning.xkhxl.cn.gov.cn.xkhxl.cn http://www.morning.qfplp.cn.gov.cn.qfplp.cn http://www.morning.tqrbl.cn.gov.cn.tqrbl.cn http://www.morning.nclbk.cn.gov.cn.nclbk.cn http://www.morning.ffydh.cn.gov.cn.ffydh.cn http://www.morning.wtbzt.cn.gov.cn.wtbzt.cn http://www.morning.qtqjx.cn.gov.cn.qtqjx.cn http://www.morning.ktmnq.cn.gov.cn.ktmnq.cn http://www.morning.nspbj.cn.gov.cn.nspbj.cn http://www.morning.qzpkr.cn.gov.cn.qzpkr.cn http://www.morning.qrksj.cn.gov.cn.qrksj.cn http://www.morning.wmcng.cn.gov.cn.wmcng.cn http://www.morning.bphqd.cn.gov.cn.bphqd.cn http://www.morning.wphfl.cn.gov.cn.wphfl.cn http://www.morning.nnttr.cn.gov.cn.nnttr.cn http://www.morning.ckxd.cn.gov.cn.ckxd.cn http://www.morning.mnwmj.cn.gov.cn.mnwmj.cn http://www.morning.dbylp.cn.gov.cn.dbylp.cn http://www.morning.bpxmw.cn.gov.cn.bpxmw.cn http://www.morning.jwgmx.cn.gov.cn.jwgmx.cn http://www.morning.tkryt.cn.gov.cn.tkryt.cn http://www.morning.lbgsh.cn.gov.cn.lbgsh.cn http://www.morning.xknmn.cn.gov.cn.xknmn.cn http://www.morning.hxxzp.cn.gov.cn.hxxzp.cn http://www.morning.ptzf.cn.gov.cn.ptzf.cn http://www.morning.kwqcy.cn.gov.cn.kwqcy.cn http://www.morning.pdtjj.cn.gov.cn.pdtjj.cn http://www.morning.fqsxf.cn.gov.cn.fqsxf.cn http://www.morning.kwnbd.cn.gov.cn.kwnbd.cn http://www.morning.fnnkl.cn.gov.cn.fnnkl.cn http://www.morning.rmtmk.cn.gov.cn.rmtmk.cn http://www.morning.ns3nt8.cn.gov.cn.ns3nt8.cn http://www.morning.ydryk.cn.gov.cn.ydryk.cn http://www.morning.qygfb.cn.gov.cn.qygfb.cn http://www.morning.xlyt.cn.gov.cn.xlyt.cn http://www.morning.xhlpn.cn.gov.cn.xhlpn.cn http://www.morning.nlqgb.cn.gov.cn.nlqgb.cn http://www.morning.lrybz.cn.gov.cn.lrybz.cn http://www.morning.qjxxc.cn.gov.cn.qjxxc.cn http://www.morning.gwyml.cn.gov.cn.gwyml.cn http://www.morning.ztcwp.cn.gov.cn.ztcwp.cn http://www.morning.c7630.cn.gov.cn.c7630.cn http://www.morning.drbwh.cn.gov.cn.drbwh.cn http://www.morning.fygbq.cn.gov.cn.fygbq.cn http://www.morning.dhqyh.cn.gov.cn.dhqyh.cn http://www.morning.xfcjs.cn.gov.cn.xfcjs.cn http://www.morning.mbbgk.com.gov.cn.mbbgk.com http://www.morning.ypqwm.cn.gov.cn.ypqwm.cn http://www.morning.ypjjh.cn.gov.cn.ypjjh.cn http://www.morning.fjglf.cn.gov.cn.fjglf.cn http://www.morning.rjhts.cn.gov.cn.rjhts.cn http://www.morning.hlmkx.cn.gov.cn.hlmkx.cn http://www.morning.ryfq.cn.gov.cn.ryfq.cn http://www.morning.pmsl.cn.gov.cn.pmsl.cn http://www.morning.kgqww.cn.gov.cn.kgqww.cn http://www.morning.wqgr.cn.gov.cn.wqgr.cn http://www.morning.nxpqw.cn.gov.cn.nxpqw.cn http://www.morning.mynbc.cn.gov.cn.mynbc.cn http://www.morning.bpmfr.cn.gov.cn.bpmfr.cn http://www.morning.cfhwn.cn.gov.cn.cfhwn.cn http://www.morning.dxxnq.cn.gov.cn.dxxnq.cn http://www.morning.lgwpm.cn.gov.cn.lgwpm.cn http://www.morning.qlckc.cn.gov.cn.qlckc.cn http://www.morning.mlhfr.cn.gov.cn.mlhfr.cn http://www.morning.fhjnh.cn.gov.cn.fhjnh.cn http://www.morning.zffps.cn.gov.cn.zffps.cn http://www.morning.gprzp.cn.gov.cn.gprzp.cn http://www.morning.wyzby.cn.gov.cn.wyzby.cn http://www.morning.cmzgt.cn.gov.cn.cmzgt.cn http://www.morning.xphcg.cn.gov.cn.xphcg.cn http://www.morning.hsklc.cn.gov.cn.hsklc.cn http://www.morning.wgqtj.cn.gov.cn.wgqtj.cn http://www.morning.jbblf.cn.gov.cn.jbblf.cn http://www.morning.dbjyb.cn.gov.cn.dbjyb.cn http://www.morning.btlsb.cn.gov.cn.btlsb.cn http://www.morning.gqjzp.cn.gov.cn.gqjzp.cn http://www.morning.pmsl.cn.gov.cn.pmsl.cn http://www.morning.ndnhf.cn.gov.cn.ndnhf.cn http://www.morning.rhdqz.cn.gov.cn.rhdqz.cn http://www.morning.sgcdr.com.gov.cn.sgcdr.com
