<=으로 문자열을 트리밍이 개 문자

Question

당신은 입력 문자열을 주어진 가정 해 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); 
} 

Answer 2

문자열의 현재 위치와 "현재 단어"를 유지하면서 현재 단어를 모두 길이> = 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)); 

Answer 3

뭔가 (내 생각, 시간 복잡도가 최적) 충분합니다 :

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

무엇 공간의 복잡성에 대해? O (k)에서 실행될 수 있습니다 (입력 및 출력의 크기를 계산할 수는 없습니다). Split은 실제 배열을 만들기 때문에 .NET에서는 그렇지 않습니다. 그러나 대신 반복자를 만들 수 있습니다. 문자열이 문자를 반복하는 것이라고 상상하면 O (1) 알고리즘이됩니다.

Answer 4

" "에 의해 split() 및 if length() <= 2

Answer 5

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

(스칼라)를 생략