algorithm - 修剪 <= 2 个字符的字符串

Question

假设给你一个输入字符串:

"my name is vikas"

建议将其修改为的算法:

"name vikas"

这意味着删除长度为 <=2 的单词或者说 k字符，使其通用。

Answer 1

我认为您可以在 O(n) 时间内就地完成此操作。遍历字符串，保留一个指向您正在处理的单词的开头的指针。如果发现单词的长度大于 k，则用该单词覆盖字符串的开头。这是一个 C 代码(它假定每个单词都由精确的空格分隔):

void modify(char *s, int k){

    int n = strlen(s);
    int j = 0, cnt = 0, r = 0, prev = -1;
    s[n++] = ' ';  // Setinel to avoid special case
    for(int i=0; i<n; i++){
        if(s[i] == ' '){
            if (cnt > k){
                if(r > 0) s[r++] = ' ';
                while(j < i) s[r++] = s[j++];
            }       
            cnt = 0;
        }
        else {
            if (prev == ' ') j = i;
            cnt++;
        }
        prev = s[i];
    }
    s[r] = '\0';
}
int main(){

    char s[] = "my name is vikas";
    modify(s, 2);
    printf("%s\n", s);
}