当前位置:   article > 正文

JAVA程序设计:前缀和后缀搜索(LeetCode:745)_前缀函数 java

前缀函数 java

给定多个 words,words[i] 的权重为 i 。

设计一个类 WordFilter 实现函数WordFilter.f(String prefix, String suffix)。这个函数将返回具有前缀 prefix 和后缀suffix 的词的最大权重。如果没有这样的词,返回 -1。

例子:

输入:
WordFilter(["apple"])
WordFilter.f("a", "e") // 返回 0
WordFilter.f("b", "") // 返回 -1
注意:

words的长度在[1, 15000]之间。
对于每个测试用例,最多会有words.length次对WordFilter.f的调用。
words[i]的长度在[1, 10]之间。
prefix, suffix的长度在[0, 10]之前。
words[i]和prefix, suffix只包含小写字母。

方法一:暴力匹配每个单词的前后缀(超时)

  1. class WordFilter {
  2. String[] words;
  3. public WordFilter(String[] words) {
  4. this.words=words;
  5. }
  6. public int f(String prefix, String suffix) {
  7. for(int i=words.length-1;i>=0;i--)
  8. if(words[i].startsWith(prefix) && words[i].endsWith(suffix))
  9. return i;
  10. return -1;
  11. }
  12. }

方法二:将前后缀合并为一个单词,加入字典树方便后续查找,其中两个单词合并为一个单词的方法有很多种。例如我们可以交叉合并,假如prefix="app",suffix="see",则合并后可以为“aepeps”,若要查询的前后缀不等长的话可以将少的部分变为none。当然我们也可以通过其他方法进行合并,方法不止一种。

  1. class WordFilter {
  2. class Tree{
  3. int val;
  4. Map<Integer,Tree> children;
  5. public Tree() {
  6. val=0;
  7. children=new HashMap<>();
  8. }
  9. }
  10. Tree root;
  11. public WordFilter(String[] words) {
  12. int weight=0;
  13. root=new Tree();
  14. for(String word : words) {
  15. Tree cur=root;
  16. cur.val=weight;
  17. int len=word.length();
  18. char[] chars=word.toCharArray();
  19. for(int i=0;i<len;i++) {
  20. Tree tmp=cur;
  21. for(int j=i;j<len;j++) {
  22. int code=(chars[j]-'`')*27;
  23. if(tmp.children.get(code)==null)
  24. tmp.children.put(code, new Tree());
  25. tmp=tmp.children.get(code);
  26. tmp.val=weight;
  27. }
  28. tmp=cur;
  29. for(int k=len-1-i;k>=0;k--) {
  30. int code=chars[k]-'`';
  31. if(tmp.children.get(code)==null)
  32. tmp.children.put(code, new Tree());
  33. tmp=tmp.children.get(code);
  34. tmp.val=weight;
  35. }
  36. int code=(chars[i]-'`')*27+(chars[len-1-i]-'`');
  37. if(cur.children.get(code)==null)
  38. cur.children.put(code, new Tree());
  39. cur=cur.children.get(code);
  40. cur.val=weight;
  41. }
  42. weight++;
  43. }
  44. }
  45. public int f(String prefix, String suffix) {
  46. Tree cur=root;
  47. int i=0,j=suffix.length()-1;
  48. while(i<prefix.length() || j>=0) {
  49. char c1=i<prefix.length()?prefix.charAt(i):'`';
  50. char c2=j>=0?suffix.charAt(j):'`';
  51. int code=(c1-'`')*27+(c2-'`');
  52. cur=cur.children.get(code);
  53. if(cur==null) return -1;
  54. i++; j--;
  55. }
  56. return cur.val;
  57. }
  58. }

 

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/神奇cpp/article/detail/871435
推荐阅读
相关标签
  

闽ICP备14008679号