资讯专栏INFORMATION COLUMN

Word Abbreviation

Y3G / 995人阅读

摘要:链接注意第一个数字是的情况,这种也是不合法的。还有一个注意的就是要想和有相同的缩写,长度必须和它相同,所以只保留长度相同的。注意剪枝,当前长度已经超过就不需要继续了。二进制的做法是这样的,先对字典里面的单词进行处理。

Valid Word Abbreviation

链接:https://leetcode.com/problems...

注意第一个数字是0的情况,["a", "01"]这种也是不合法的。

</>复制代码

  1. public class Solution {
  2. public boolean validWordAbbreviation(String word, String abbr) {
  3. /* while loop, i for word, j for abbr
  4. * if it is number: count the number
  5. * i += number
  6. * else: compare word.charAt(i) == abbr.charAt(j)
  7. * end: i < len(word) && j < len(abbr)
  8. * return i == len(word) && j == len(abbr)
  9. */
  10. int i = 0, j = 0;
  11. while(i < word.length() && j < abbr.length()) {
  12. // character
  13. if(abbr.charAt(j) > "9" || abbr.charAt(j) <= "0") {
  14. // characters not same
  15. if(word.charAt(i) != abbr.charAt(j)) return false;
  16. i++; j++;
  17. }
  18. // count number
  19. else {
  20. int count = 0;
  21. while(j < abbr.length() && Character.isDigit(abbr.charAt(j))) {
  22. count = 10 * count + (abbr.charAt(j) - "0");
  23. j++;
  24. }
  25. i += count;
  26. }
  27. }
  28. return i == word.length() && j == abbr.length();
  29. }
  30. }

</>复制代码

  1. // if number:
  2. // if character: check the same
  3. int i = 0;
  4. int m = word.length(), n = abbr.length();
  5. int count = 0;
  6. for(int j = 0; j < abbr.length(); j++) {
  7. char c = abbr.charAt(j);
  8. // number
  9. if(c >= "0" && c <= "9") {
  10. if(count == 0 && c == "0") return false;
  11. count = count * 10 + (c - "0");
  12. }
  13. // digit
  14. else {
  15. i += count;
  16. if(i >= word.length() || word.charAt(i) != c) return false;
  17. count = 0;
  18. i++;
  19. }
  20. }
  21. return i + count == m;
Minimum Unique Word Abbreviation

题目链接:https://leetcode.com/problems...

又是一道backtracking的题。看了这个博客的解法:
http://bookshadow.com/weblog/...

现在是穷举可能的结果,注意prune,然后check是否有和dict相同的。还有一个注意的就是要想和target有相同的缩写,长度必须和它相同,所以dict只保留长度相同的。注意剪枝,当前长度已经超过globalMin就不需要继续了。

</>复制代码

  1. public class Solution {
  2. public String minAbbreviation(String target, String[] dictionary) {
  3. // only keep the words has the same length
  4. int len = target.length();
  5. for(String s : dictionary) {
  6. if(s.length() == len) dict.add(s);
  7. }
  8. // no word has the same length as target
  9. if(dict.isEmpty()) return String.valueOf(target.length());
  10. globalMin = len;
  11. global = target;
  12. dfs(target, 0, 0, "");
  13. return global;
  14. }
  15. Set dict = new HashSet();
  16. int globalMin;
  17. String global;
  18. private void dfs(String target, int index, int len, String abbr) {
  19. // pruning
  20. if(len >= globalMin) return;
  21. // base case
  22. if(index == target.length()) {
  23. for(String word : dict) {
  24. if(validWordAbbreviation(word, abbr)) return;
  25. }
  26. globalMin = len;
  27. global = abbr;
  28. return;
  29. }
  30. // 2 subproblems:
  31. // 1. target[i] = char
  32. // 2. target[i] = num
  33. dfs(target, index + 1, len + 1, abbr + target.charAt(index));
  34. int abbr_len = abbr.length();
  35. if(index == 0 || !Character.isDigit(abbr.charAt(abbr_len - 1))) {
  36. dfs(target, index + 1, len + 1, abbr + 1);
  37. }
  38. else {
  39. int num = 1 + (abbr.charAt(abbr_len - 1) - "0");
  40. dfs(target, index + 1, len, abbr.substring(0, abbr_len-1) + num);
  41. }
  42. }
  43. private boolean validWordAbbreviation(String word, String abbr) {
  44. // if number:
  45. // if character: check the same
  46. int i = 0;
  47. int m = word.length(), n = abbr.length();
  48. int count = 0;
  49. for(int j = 0; j < abbr.length(); j++) {
  50. char c = abbr.charAt(j);
  51. // number
  52. if(c >= "0" && c <= "9") {
  53. if(count == 0 && c == "0") return false;
  54. count = count * 10 + (c - "0");
  55. }
  56. // digit
  57. else {
  58. i += count;
  59. if(i >= word.length() || word.charAt(i) != c) return false;
  60. count = 0;
  61. i++;
  62. }
  63. }
  64. return i + count == m;
  65. }
  66. }

还有bit的方法,感觉好厉害!!完全没想出来。
二进制的做法是这样的,先对字典里面的单词进行处理。一个char一个char处理,如果该char和target对应位置上的一样,则记为1,否则记为0,这样处理完之后就知道哪些位置上的字母可以换成数字。对target进行缩写的时候,保留字母的记为1,换成数字的记为0,这样查target的abbr是否是word的缩写时,只需要把两者相与看是否和abbr相同即可。
我还是没搞懂这个到底是怎么想出来的,明天再看看。

</>复制代码

  1. public class Solution {
  2. public String minAbbreviation(String target, String[] dictionary) {
  3. len = target.length();
  4. globalMin = target.length()+1;
  5. global = 0;
  6. getBitDict(target, dictionary);
  7. // edge case: target in dict, no word with same len
  8. if(globalMin == 0) return target;
  9. if(dict.size() == 0) return String.valueOf(len);
  10. // backtracking
  11. dfs(0, 0, 0);
  12. return bitToString(target);
  13. }
  14. List dict = new ArrayList();
  15. int globalMin;
  16. int global;
  17. int len;
  18. private void dfs(int index, int curLen, int abbr) {
  19. // prune
  20. if(curLen >= globalMin) return;
  21. // base case
  22. if(index == len) {
  23. for(int word : dict) {
  24. if((word & abbr) == abbr) return;
  25. }
  26. globalMin = curLen;
  27. global = abbr;
  28. return;
  29. }
  30. // 1. character
  31. dfs(index + 1, curLen + 1, (abbr << 1) + 1);
  32. // 2. number
  33. if(index == 0 || (abbr%2) == 1) dfs(index + 1, curLen + 1, (abbr << 1));
  34. else dfs(index + 1, curLen, (abbr << 1));
  35. }
  36. private void getBitDict(String target, String[] dictionary) {
  37. // bit: 1. s[i] == target[i] => 1
  38. // 2. s[i] != target[i] => 0
  39. int len = target.length();
  40. for(String s : dictionary) {
  41. if(s.length() == len) {
  42. // edge case
  43. if(s.equals(target)) {
  44. globalMin = 0;
  45. return;
  46. }
  47. int bitString = 0;
  48. for(int i = 0; i < len; i++) {
  49. bitString = bitString << 1;
  50. if(target.charAt(i) == s.charAt(i)) bitString += 1;
  51. }
  52. dict.add(bitString);
  53. }
  54. }
  55. }
  56. private String bitToString(String target) {
  57. String result = "";
  58. int count = 0;
  59. for(int i = 0; i < len; i++) {
  60. if(((global >> len - i - 1) & 1) == 1) {
  61. if(count != 0) result += count;
  62. count = 0;
  63. result += target.charAt(i);
  64. }
  65. else count++;
  66. }
  67. if(count != 0) result += count;
  68. return result;
  69. }
  70. }

练习白板第一天,板子买小了。思路写的也不整齐,擦了好几次,大概写了30分钟,还需要多多练习额。。dfs的题,下次写的时候,还是按照start -> arguments&return type -> base case -> subproblem的顺序来,pruning最后添上。明天研究性下怎么写时间复杂度的。

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/66565.html

相关文章

  • Unique Word Abbreviation LC解题记录

    摘要:题目内容这题也是锁住的,通过率只有左右。另外,字典里面只有两个的时候,也是返回。最后再说两句距离上一篇文章过了一段时间了,这段时间搬家再适应新环境,解决心理问题。 题目内容 An abbreviation of a word follows the form . Below are some examples of word abbreviations: a) it ...

    curried 评论0 收藏0
  • [LeetCode] 408. Valid Word Abbreviation

    Problem Given a non-empty string s and an abbreviation abbr, return whether the string matches with the given abbreviation. A string such as word contains only the following valid abbreviations: [word...

    zone 评论0 收藏0
  • 320. Generalized Abbreviation

    摘要:题目链接要输出所有的结果,标准思路。也可以做,保留为,改为数字的为,然后结果就是这么多,每个数学遍历一遍求对应的即可。 320. Generalized Abbreviation 题目链接:https://leetcode.com/problems... 要输出所有的结果,backtracking标准思路。 public class Solution { public List...

    yangrd 评论0 收藏0
  • 320. Generalized Abbreviation and 22. Generate Par

    320 Generalized Abbreviation public class Solution { public List generateAbbreviations(String word) { List res = new ArrayList(); backtrack(res, word, 0, , 0); return res; ...

    lanffy 评论0 收藏0
  • [LeetCode]Generalized Abbreviation

    摘要:分析这道题第一步一定要理解题意,首先要考虑的是会有多少种结果。仔细观察会发现,最终会有种结果。然后就很显然应该用每次存下当前结果,然后继续。 Generalized Abbreviation Write a function to generate the generalized abbreviations of a word. Example:Given word = word, ...

    ZoomQuiet 评论0 收藏0

发表评论

0条评论

Y3G

|高级讲师

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<