Função C ++ para contar todas as palavras em uma string

Fui perguntado isso durante uma entrevista e, aparentemente, é uma pergunta fácil, mas não foi e ainda não é óbvio para mim.

Dada uma string, conte todas as palavras nela. Não importa se eles são repetidos. Apenas a contagem total como em uma contagem de palavras de arquivos de texto. As palavras são separadas por um espaço e a pontuação não importa, contanto que seja parte de uma palavra.

Por exemplo: 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

Meu “algoritmo” simplesmente passa por procurar espaços e incrementar um contador até eu atingir um valor nulo. Desde que eu não consegui o emprego e foi convidado a sair depois que eu acho que a minha solução não foi boa? Alguém tem uma solução mais inteligente? Estou esquecendo de algo?

Um método menos inteligente, mais óbvio para todos os programadores da sua equipe.

 #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; } 

Supondo que as palavras sejam separadas por espaços em branco:

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

Nota: Pode haver mais de um espaço entre as palavras. Além disso, isso não captura outros caracteres de espaço em branco, como aba nova linha ou retorno de carro. Então contando espaços não é suficiente.

O operador de input de stream >> quando usado para ler uma cadeia de caracteres de um stream. Lê uma palavra separada em branco. Então eles provavelmente estavam procurando por você para usar isso para identificar palavras.

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

Quando pode usar isso para contar palavras em uma string.

 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. 

Ficando complicado:
Os streams podem ser tratados como qualquer outro contêiner e há iteradores para fazer um loop entre eles std :: istream_iterator. Quando você usa o operador ++ em um istream_iterator, apenas lê o próximo valor do stream usando o operador >>. Neste caso, estamos lendo std :: string para ler uma palavra separada por espaço.

 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; } 

O uso de std :: distance apenas envolve todos os itens acima em um pacote arrumado, pois ele encontra a distância entre dois iteradores, fazendo ++ no primeiro até chegarmos ao segundo.

Para evitar copiar a string, podemos ser sorrateiros:

 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: ainda copiamos cada palavra do original para um temporário. Mas o custo disso é mínimo.

Outra solução baseada em boost que pode funcionar (não testada):

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

Mais informações podem ser encontradas na Biblioteca de Algoritmos de Cadeia de Boost

Isso pode ser feito sem olhar manualmente todos os caracteres ou copiar a string.

 #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; 

Tomei a liberdade de usar isalnum vez de isspace .

Isso não é algo que eu faria em uma entrevista de emprego. (Não é como compilado pela primeira vez.)

Ou, para todos os inimigos 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; 

Você pode usar o std :: count ou std :: count_if para fazer isso. Abaixo um exemplo simples com 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; } 

Uma solução O (N) que também é muito simples de entender e implementar:

(Eu não verifiquei uma input de string vazia. Mas tenho certeza que você pode fazer isso facilmente.)

 #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 : "< 

Uma abordagem muito concisa O (N):

 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; } 

Uma abordagem de divisão e conquista, a complexidade também é 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); } 

Um algoritmo de passagem única para este problema pode ser o seguinte:

  1. Se a string estiver vazia, retorne 1
  2. deixar transições = número de pares de char adjacentes (c1, c2) em que c1 == ' ' e c2 != ' '
  3. se a frase começar com um espaço, retorne as transitions mais retorne transitions + 1

Aqui está um exemplo com string = “Um cão muito, muito, muito, muito grande comeu meu dever de casa !!!!”

  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 

Explicação

 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 

Esse algoritmo manipula os casos com vários espaços corretamente

Aqui estão duas soluções que eu criei

Solução ingênua

 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; } 

Se você pensar com cuidado, poderá reduzir esse conjunto de operações em um produto interno, que é o que foi feito abaixo.

Solução de produção interna

 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; }