Función C ++ para contar todas las palabras en una cadena

Me lo preguntaron durante una entrevista y, aparentemente, es una pregunta fácil, pero no fue ni es obvio para mí.

Dada una cuerda, cuente todas las palabras en ella. No importa si se repiten. Solo el conteo total como en un recuento de palabras de archivos de texto. Las palabras son cualquier cosa separada por un espacio y la puntuación no importa, siempre que sea parte de una palabra.

Por ejemplo: ¡ A very, very, very, very, very big dog ate my homework!!!! ==> 11 words A very, very, very, very, very big dog ate my homework!!!! ==> 11 words

Mi “algoritmo” simplemente busca espacios e incrementa un contador hasta que toco un nulo. Como no conseguí el trabajo y me pidieron que me fuera después de eso, ¿supongo que mi solución no fue buena? Alguien tiene una solución más inteligente? ¿Me estoy perdiendo de algo?

Un método menos inteligente, más obvio para todos los progtwigdores en su equipo para hacerlo.

 #include  int CountWords(const char* str) { if (str == NULL) return error_condition; // let the requirements define this... bool inSpaces = true; int numWords = 0; while (*str != NULL) { if (std::isspace(*str)) { inSpaces = true; } else if (inSpaces) { numWords++; inSpaces = false; } ++str; } return numWords; } 

Suponiendo que las palabras estén separadas por espacios en blanco:

 unsigned int countWordsInString(std::string const& str) { std::stringstream stream(str); return std::distance(std::istream_iterator(stream), std::istream_iterator()); } 

Nota: Puede haber más de un espacio entre palabras. Además, esto no capta otros caracteres de espacio en blanco, como tabulación nueva línea o retorno de carro. Entonces contar espacios no es suficiente.

El operador de entrada de secuencia >> cuando se usa para leer una cadena de una secuencia. Lee una palabra separada en blanco. Probablemente buscaban que lo usara para identificar palabras.

 std::stringstream stream(str); std::string oneWord; stream >> oneWord; // Reads one space separated word. 

Cuando puede usar esto para contar palabras en una cadena.

 std::stringstream stream(str); std::string oneWord; unsigned int count = 0; while(stream >> oneWord) { ++count;} // count now has the number of words in the string. 

Conseguir complicado:
Los flujos se pueden tratar como cualquier otro contenedor y hay iteradores para recorrerlos en std :: istream_iterator. Cuando usas el operador ++ en un istream_iterator, solo lees el siguiente valor de la secuencia usando el operador >>. En este caso, estamos leyendo std :: string para que lea una palabra separada del espacio.

 std::stringstream stream(str); std::string oneWord; unsigned int count = 0; std::istream_iterator loop = std::istream_iterator(stream); std::istream_iterator end = std::istream_iterator(); for(;loop != end; ++count, ++loop) { *loop; } 

El uso de std :: distance simplemente envuelve todo lo anterior en un paquete ordenado, ya que encuentra la distancia entre dos iteradores al hacer ++ en el primero hasta que llegamos al segundo.

Para evitar copiar la cadena, podemos ser astutos:

 unsigned int countWordsInString(std::string const& str) { std::stringstream stream; // sneaky way to use the string as the buffer to avoid copy. stream.rdbuf()->pubsetbuf (str.c_str(), str.length() ); return std::distance(std::istream_iterator(stream), std::istream_iterator()); } 

Nota: aún copiamos cada palabra del original en una temporal. Pero el costo de eso es mínimo.

Otra solución basada en impulso que puede funcionar (no probada):

 vector result; split(result, "aaaa bbbb cccc", is_any_of(" \t\n\v\f\r"), token_compress_on); 

Se puede encontrar más información en la Biblioteca de Algoritmos Boost String

Esto se puede hacer sin mirar manualmente cada carácter o copiar la cadena.

 #include  #include  boost::transform_iterator < int (*)(int), std::string::const_iterator, bool const& > pen( str.begin(), std::isalnum ), end( str.end(), std::isalnum ); size_t word_cnt = 0; while ( pen != end ) { word_cnt += * pen; pen = std::mismatch( pen+1, end, pen ).first; } return word_cnt; 

Me tomé la libertad de usar isalnum lugar de isspace .

Esto no es algo que haría en una entrevista de trabajo. (No es como comstackdo la primera vez).

O, para todos los enemigos de Boost; v)

 if ( str.empty() ) return 0; size_t word_cnt = std::isalnum( * str.begin() ); for ( std::string::const_iterator pen = str.begin(); ++ pen != str.end(); ) { word_cnt += std::isalnum( pen[ 0 ] ) && ! std::isalnum( pen[ -1 ] ); } return word_cnt; 

Puede usar std :: count o std :: count_if para hacer eso. Debajo de un ejemplo simple con std :: count:

 //Count the number of words on string #include  #include  #include  //count and count_if is declared here int main () { std::string sTEST("Text to verify how many words it has."); std::cout << std::count(sTEST.cbegin(), sTEST.cend(), ' ')+1; return 0; } 

Una solución O (N) que también es muy simple de comprender e implementar:

(No he verificado la entrada de una cadena vacía, pero estoy seguro de que puedes hacerlo fácilmente).

 #include  #include  using namespace std; int countNumberOfWords(string sentence){ int numberOfWords = 0; size_t i; if (isalpha(sentence[0])) { numberOfWords++; } for (i = 1; i < sentence.length(); i++) { if ((isalpha(sentence[i])) && (!isalpha(sentence[i-1]))) { numberOfWords++; } } return numberOfWords; } int main() { string sentence; cout<<"Enter the sentence : "; getline(cin, sentence); int numberOfWords = countNumberOfWords(sentence); cout<<"The number of words in the sentence is : "< 

Un enfoque O (N) muy conciso:

 bool is_letter(char c) { return c >= 'a' && c <= 'z' || c >= 'A' && c <= 'Z'; } int count_words(const string& s) { int i = 0, N = s.size(), count = 0; while(i < N) { while(i < N && !is_letter(s[i])) i++; if(i == N) break; while(i < N && is_letter(s[i])) i++; count++; } return count; } 

Un enfoque de dividir y vencer, la complejidad también es O (N):

 int DC(const string& A, int low, int high) { if(low > high) return 0; int mid = low + (high - low) / 2; int count_left = DC(A, low, mid-1); int count_right = DC(A, mid+1, high); if(!is_letter(A[mid])) return count_left + count_right; else { if(mid == low && mid == high) return 1; if(mid-1 < low) { if(is_letter(A[mid+1])) return count_right; else return count_right+1; } else if(mid+1 > high) { if(is_letter(A[mid-1])) return count_left; else return count_left+1; } else { if(!is_letter(A[mid-1]) && !is_letter(A[mid+1])) return count_left + count_right + 1; else if(is_letter(A[mid-1]) && is_letter(A[mid+1])) return count_left + count_right - 1; else return count_left + count_right; } } } int count_words_divide_n_conquer(const string& s) { return DC(s, 0, s.size()-1); } 

Un algoritmo de pase único para este problema puede ser el siguiente:

  1. Si la cadena está vacía, devuelve 1
  2. let transitions = número de pares de caracteres adyacentes (c1, c2) donde c1 == ' ' y c2 != ' '
  3. si la oración comienza con un espacio, las transitions retorno devuelven las transitions + 1

Aquí hay un ejemplo con string = “¡Un perro muy, muy, muy, muy, muy grande comió mi tarea!”

  i | 0123456789 c2 | A very, very, very, very, very big dog ate my homework!!!! c1 | A very, very, very, very, very big dog ate my homework!!!! | xxxxxxxxxx 

Explicación

 Let `i` be the loop counter. When i=0: c1='A' and c2=' ', the condition `c1 == ' '` and `c2 != ' '` is not met When i=1: c1=' ' and c2='A', the condition is met ... and so on for the remaining characters 

Este algoritmo maneja los casos con múltiples espacios adecuadamente

Aquí hay 2 soluciones que se me ocurrieron

Solución ingenua

 size_t count_words_naive(const std::string_view& s) { if (s.size() == 0) return 0; size_t count = 0; bool isspace1, isspace2 = true; for (auto c : s) { isspace1 = std::exchange(isspace2, isspace(c)); count += (isspace1 && !isspace2); } return count; } 

Si piensas detenidamente, podrás reducir este conjunto de operaciones en un producto interno, que es lo que se ha hecho a continuación.

Solución de producto interno

 size_t count_words_using_inner_prod(const std::string_view& s) { if (s.size() == 0) return 0; auto starts_with_space = isspace(s.front()); auto num_transitions = std::inner_product( s.begin()+1, s.end(), s.begin(), 0, std::plus<>(), [](char c2, char c1) { return isspace(c1) && !isspace(c2); }); return num_transitions + !starts_with_space; }