朝阳无限好 - Morning Sun Community

 找回密码
 注册
查看: 253|回复: 2

[中等] 394. 字符串解码

[复制链接]
发表于 2020-3-29 23:48:00 | 显示全部楼层 |阅读模式
给定一个经过编码的字符串,返回它解码后的字符串。

编码规则为: k[encoded_string],表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的;输入字符串中没有额外的空格,且输入的方括号总是符合格式要求的。

此外,你可以认为原始数据不包含数字,所有的数字只表示重复的次数 k ,例如不会出现像 3a 或 2[4] 的输入。

示例:

s = "3[a]2[bc]", 返回 "aaabcbc".
s = "3[a2[c]]", 返回 "accaccacc".
s = "2[abc]3[cd]ef", 返回 "abcabccdcdcdef".

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/decode-string
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
 楼主| 发表于 2020-3-29 23:48:37 | 显示全部楼层
  1. int GetWeiShu(int num)
  2. {
  3.     int i = 1;

  4.     while (num >= 10) {
  5.         num = num / 10;
  6.         i++;
  7.     }
  8.     return i;
  9. }

  10. int GetLen(char * s, char *end)
  11. {
  12.     int i, j, k, len, stringLen;
  13.     char *pos;
  14.     char *posTmp;
  15.     char *posTmp2;
  16.     if (!s || !s[0]) {
  17.         return 0;
  18.     }
  19.     stringLen = strlen(s);
  20.     //printf("s=%lx, end=%lx\n", s, end);
  21.     if (!end) {
  22.         end = &s[stringLen - 1];
  23.     }
  24.     for (i = 0, j = 0; &s[i] <= end; i++) {
  25.         if ((s[i] >= '0') && (s[i] <= '9')) {
  26.             k=atoi(&s[i]);
  27.             i += (GetWeiShu(k) + 1);
  28.             posTmp = strchr(&s[i], ']');
  29.             pos = posTmp;
  30.             posTmp2 = strchr(&s[i], '[');;
  31.             while ((posTmp != NULL) && (posTmp < end) && ((posTmp2 != NULL) && (posTmp2 < posTmp))) {
  32.                 posTmp = strchr(posTmp+1, ']');
  33.                 pos = posTmp;
  34.                 posTmp2 = strchr(posTmp2+1, '[');;
  35.             }
  36.             //len = pos - &s[i];
  37.             len = GetLen(&s[i], pos - 1);
  38.             j += (k * len);
  39.             i += (pos - &s[i]);
  40.         } else {
  41.             j++;
  42.         }
  43.     }
  44.     //for (i = 0; &s[i] <= end; i++) {
  45.     //    printf("%c", s[i]);
  46.     //}
  47.     //printf(", len is %d, s=%s, end-s=%d\n", j, s, end-s);
  48.     return j;
  49. }

  50. char * decodeStringNew(char * s, char *end){
  51.     int len = GetLen(s, end);
  52.     char *result;
  53.     char *pos;
  54.     char *posTmp;
  55.     char *posTmp2;
  56.     char *decodeTmp;
  57.     int i, j, k, m, tmp, stringLen;
  58.     if (!len) {
  59.         result = (char*)malloc(1);
  60.         result[0] = 0;
  61.         return result;
  62.     }
  63.     stringLen = strlen(s);
  64.     if (!end) {
  65.         end = &s[stringLen - 1];
  66.     }
  67.     //printf("len is %d\n", len);
  68.     result = (char*)malloc(len+1);
  69.     memset(result, 0, len+1);
  70.     for (i = 0, j = 0; &s[i] <= end; i++) {
  71.         if ((s[i] >= '0') && (s[i] <= '9')) {
  72.             k=atoi(&s[i]);
  73.             i += (GetWeiShu(k) + 1);
  74.             posTmp = strchr(&s[i], ']');
  75.             pos = posTmp;
  76.             posTmp2 = strchr(&s[i], '[');;
  77.             while ((posTmp != NULL) && (posTmp < end) && ((posTmp2 != NULL) && (posTmp2 < posTmp))) {
  78.                 posTmp = strchr(posTmp+1, ']');
  79.                 pos = posTmp;
  80.                 posTmp2 = strchr(posTmp2+1, '[');;
  81.             }
  82.             decodeTmp = decodeStringNew(&s[i], pos - 1);
  83.             tmp = strlen(decodeTmp);
  84.             for (m = 0; m < k; m++) {
  85.                 strncpy(&result[j], decodeTmp, tmp);
  86.                 j += tmp;
  87.             }
  88.             i += (pos - &s[i]);
  89.             free(decodeTmp);
  90.         } else {
  91.             result[j] = s[i];
  92.             j++;
  93.         }
  94.     }
  95.     return result;
  96. }

  97. char * decodeString(char * s){
  98.     return decodeStringNew(s, NULL);
  99. }
复制代码

执行结果:通过
显示详情

执行用时 :0 ms, 在所有 C 提交中击败了100.00%的用户
内存消耗 :5.6 MB, 在所有 C 提交中击败了100.00%的用户
回复 支持 反对

使用道具 举报

 楼主| 发表于 2020-3-29 23:52:02 | 显示全部楼层
"100[leetcode]"
"3[a2[c]]"


输入:""
预期:""

回复 支持 反对

使用道具 举报

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

本版积分规则

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

GMT+8, 2020-10-25 09:28 , Processed in 0.048597 second(s), 16 queries .

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