剪裁字符串与<= 2个字符

假设你给出一个输入字符串：剪裁字符串与<= 2个字符

"my name is vikas"

推荐的算法将其修改到：

"name vikas"

这意味着除去具有长度<=2词语或说k个字符，以使其通用。

来源

2011-01-20 Vikas

最好的答案是语言相关的。这不是语言不可知的。 – marcog 2011-01-20 11:45:55

@Colin [请勿编辑问题以添加作业标签。如果有任何疑问，最好保留原样。相反，首先添加注释，要求提问者澄清情况。]（http://meta.stackexchange.com/questions/10811/how-to-ask-and-answer-homework-questions） – marcog 2011-01-20 11:47:15

我觉得你可以在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); 
}

来源

2011-01-20 12:44:28 kunigami

遍历保持字符串中的当前位置和“当前字”，累加所有当前字长度> = K字符串的各个字符，从累积词语重新组装字符串？

该算法采用就地重写，最大限度地减少副本的元素之间的数字：

final int k = 2; 

    char[] test = "  my name  is el jenso ".toCharArray(); 
    int l = test.length; 
    int pos = 0; 
    int cwPos = 0; 
    int copyPos = 0; 

    while (pos < l) 
    { 
     if (Character.isWhitespace(test[pos])) 
     { 
      int r = pos - cwPos; 
      if (r - 1 < k) 
      { 
       copyPos -= r; 
       cwPos = ++pos; 
      } 
      else 
      { 
       cwPos = ++pos; 
       test[copyPos++] = ' '; 
      } 
     } 
     else 
     { 
      test[copyPos++] = test[pos++]; 
     } 
    } 

    System.out.println(new String(test, 0, copyPos));

来源

2011-01-20 11:51:59 eljenso

类似的东西就足够了（时间复杂度为最佳，我猜）：

input 
.Split(' ') 
.Where(s => s.Length > k) 
.Aggregate(new StringBuilder(), (sb, s) => sb.Append(s)) 
.ToString()

什么关于空间复杂性？那么，这可以运行在O（k）（当然，我们不能计算输入和输出的大小），如果你想一想。它不会在.NET中，因为Split会生成实际的数组。但是你可以改用迭代器。如果你想象这个字符串只是迭代字符，它将变成O（1）算法。

来源

2011-01-20 11:57:00

split()通过" "，省略if length() <= 2

来源

2011-01-20 12:04:30

"a short sentence of words" split ' ' filter {_.length > 2} mkString " "

（斯卡拉）

来源

2011-01-20 12:15:24

剪裁字符串与<= 2个字符

回答

相关问题