朝阳无限好 - Morning Sun Community

 找回密码
 注册
查看: 75|回复: 1

[中等] 820. 单词的压缩编码

[复制链接]
发表于 2020-3-22 15:29:37 | 显示全部楼层 |阅读模式
给定一个单词列表,我们将这个列表编码成一个索引字符串 S 与一个索引列表 A。

例如,如果这个列表是 ["time", "me", "bell"],我们就可以将其表示为 S = "time#bell#" 和 indexes = [0, 2, 5]。

对于每一个索引,我们可以通过从字符串 S 中索引的位置开始读取字符串,直到 "#" 结束,来恢复我们之前的单词列表。

那么成功对给定单词列表进行编码的最小字符串长度是多少呢?



示例:

输入: words = ["time", "me", "bell"]
输出: 10
说明: S = "time#bell#" , indexes = [0, 2, 5] 。


提示:

1 <= words.length <= 2000
1 <= words.length <= 7
每个单词都是小写字母 。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/short-encoding-of-words
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

 楼主| 发表于 2020-3-22 15:30:52 | 显示全部楼层
  1. int Compare(char *string1, int len1, char *string2, int len2)
  2. {
  3.     int i, j;
  4.     for (i = len1, j = len2; i >= 0 && j >= 0; i--, j--) {
  5.         if (string1[i] != string2[j]) {
  6.             return -1;
  7.         }
  8.     }
  9.     if (i < 0) {
  10.         if (j < 0) {
  11.             return 0; /* 相同 */
  12.         }
  13.         return 2; /* 2包含1 */
  14.     }
  15.     return 1; /* 1包含2 */
  16. }

  17. void Insert(char **atest, char *string, int *index, int *alen)
  18. {
  19.     int len1, len2;
  20.     int i;
  21.     int ret;

  22.     len2 = strlen(string);
  23.     for (i = 0; i < *index; i++) {
  24.         len1 = alen[i];
  25.         ret = Compare(atest[i], len1, string, len2);
  26.         if ((ret == 0) || (ret == 1)) {
  27.             return;
  28.         } else if (ret == 2) {
  29.             strcpy(atest[i], string);
  30.             alen[i] = len2;
  31.             return;
  32.         }
  33.     }
  34.     strcpy(atest[i], string);
  35.     alen[i] = len2;
  36.     (*index)++;
  37. }

  38. int GetLen(char **atest, int index, int *alen)
  39. {
  40.     int i;
  41.     int len = 0;

  42.     for (i = 0; i < index; i++) {
  43.         len += (alen[i] + 1);
  44.     }
  45.     return len;
  46. }

  47. int minimumLengthEncoding(char ** words, int wordsSize){
  48.     char **atest;
  49.     int *alen;
  50.     int ret;
  51.     int i, j;
  52.     int index = 0;
  53.     int maxSize = 7 + 1;

  54.     if (!wordsSize || !words || !words[0]) {
  55.         return 0;
  56.     }
  57.     atest = (char **)malloc(wordsSize * sizeof(char*));
  58.     alen = (int *)malloc(wordsSize * sizeof(int));
  59.     for (i = 0; i < wordsSize; i++) {
  60.         atest[i] = (char*)malloc(maxSize);
  61.         memset(atest[i], 0, maxSize);
  62.         alen[i] = 0;
  63.     }

  64.     for (i = 0; i < wordsSize; i++) {
  65.         Insert(atest, words[i], &index, alen);
  66.     }
  67.     ret = GetLen(atest, index, alen);

  68.     for (i = 0; i < wordsSize; i++) {
  69.         free(atest[i]);
  70.         atest[i] = NULL;
  71.     }
  72.     free(atest);
  73.     free(alen);
  74.     atest = NULL;
  75.     return ret;
  76. }
复制代码

执行结果:通过
显示详情

执行用时 :568 ms, 在所有 C 提交中击败了51.28%的用户
内存消耗 :9.6 MB, 在所有 C 提交中击败了28.43%的用户


回复 支持 反对

使用道具 举报

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

本版积分规则

QQ|小黑屋|手机版|Archiver|朝阳无限好 ( 琼ICP备19005269号-1 )

GMT+8, 2020-7-7 16:06 , Processed in 0.043033 second(s), 16 queries .

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