|
【
给定一个单词列表，我们将这个列表编码成一个索引字符串 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[i].length <= 7
每个单词都是小写字母 。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/short-encoding-of-words
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
】
还是那句话，看到数组考虑排序，排序用qsort。
不过这道题是二维字符串数组，qsort第三个参数是sizeof(char *)，然后comp函数也要注意char *pa = *(char **)a。
这道题思路便是：按照数组长度降序排列，然后strstr库函数判断字符串是否是前面字符串字串。如果不是，那么retsum加上字符串长度。
int comp(const void *a, const void *b) {
char *pa = *(char **)a;
char *pb = *(char **)b;
return strlen(pb) - strlen(pa);
}
int minimumLengthEncoding(char ** words, int wordsSize){
int i, j;
int retsum;
int findflag;
char *find = NULL;
qsort(words, wordsSize, sizeof(char *), comp);
retsum = strlen(words[0]) + 1;
for (i = 1; i < wordsSize; i++) {
findflag = 0;
for (j = 0 ; j < i; j++) {
find = strstr(words[j], words[i]);
if ((find != NULL) && (strlen(find) == strlen(words[i]))) {
findflag = 1;
break;
}
}
if (findflag == 0) {
retsum += strlen(words[i]) + 1;
}
}
return retsum;
}
| 
转播
