Frage C ++ - Funktion, um alle Wörter in einer Zeichenfolge zu zählen


Ich wurde das während eines Interviews gefragt und anscheinend ist es eine einfache Frage, aber es war nicht und ist immer noch nicht für mich offensichtlich.

Bei einer gegebenen Zeichenfolge zählen Sie alle Wörter. Es macht nichts, wenn sie wiederholt werden. Nur die Gesamtzahl zählt wie in einer Textdatei Wortanzahl. Wörter sind alles durch einen Raum getrennt und Interpunktion spielt keine Rolle, solange es Teil eines Wortes ist.

Beispielsweise: A very, very, very, very, very big dog ate my homework!!!! ==> 11 words

Mein "Algorithmus" sucht nur nach Leerzeichen und erhöht einen Zähler, bis ich eine Null erreiche. Da ich den Job nicht bekommen habe und danach gebeten wurde zu gehen, denke ich, dass meine Lösung nicht gut war? Hat jemand eine cleverere Lösung? Fehle ich etwas?


12
2017-09-08 22:02


Ursprung


Antworten:


Eine weniger clevere, offenere Methode für all die Programmierer im Team.

#include <cctype>

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

7
2017-09-08 22:30



Angenommen, Wörter sind Leerzeichen getrennt:

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

Hinweis: Zwischen den Wörtern kann mehr Platz sein. Außerdem werden andere Leerzeichen wie Tabulatorzeile oder Wagenrücklauf nicht abgefangen. Das Zählen von Räumen ist nicht genug.

Der Stream-Eingabeoperator >>, wenn er zum Lesen einer Zeichenfolge aus einem Stream verwendet wird. Liest ein Wort mit Leerzeichen getrennt. Wahrscheinlich suchten sie nach dir, um damit Wörter zu identifizieren.

std::stringstream  stream(str);
std::string        oneWord;

stream >> oneWord; // Reads one space separated word.

Wann kann dies verwendet werden, um Wörter in einer Zeichenfolge zu zählen.

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.

Kompliziert werden:
Streams können genau wie alle anderen Container behandelt werden und es gibt Iteratoren, die sie durchlaufen können std :: iStream_iterator. Wenn Sie den Operator ++ auf einem istream_iterator verwenden, liest er einfach den nächsten Wert aus dem Stream mit dem Operator >>. In diesem Fall lesen wir std :: string, um ein Leerzeichen zu lesen.

std::stringstream  stream(str);
std::string        oneWord;
unsigned int       count = 0;

std::istream_iterator loop = std::istream_iterator<std::string>(stream);
std::istream_iterator end  = std::istream_iterator<std::string>();

for(;loop != end; ++count, ++loop) { *loop; }

Die Verwendung von std :: distance umschließt einfach alles oben in einem ordentlichen Paket, da es den Abstand zwischen zwei Iteratoren durch Ausführen von ++ auf der ersten findet, bis wir die zweite erreichen.

Um das Kopieren der Zeichenfolge zu vermeiden, können wir hinterhältig sein:

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<std::string>(stream), std::istream_iterator<std::string>());
}

Hinweis: Wir kopieren immer noch jedes Wort aus dem Original in ein temporäres. Aber die Kosten dafür sind minimal.


31
2017-09-08 22:07



Eine weitere Boost-basierte Lösung, die möglicherweise funktioniert (ungetestet):

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

Weitere Informationen finden Sie in der Boost-String-Algorithmen-Bibliothek


4
2017-09-09 02:01



Dies kann durchgeführt werden, ohne jedes Zeichen manuell zu betrachten oder die Zeichenfolge zu kopieren.

#include <boost/iterator/transform_iterator.hpp>
#include <cctype>

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;

Ich habe mir erlaubt, zu benutzen isalnum Anstatt von isspace.

Das würde ich bei einem Vorstellungsgespräch nicht tun. (Es ist nicht so wie es beim ersten Mal kompiliert wurde.)

Oder für alle Boost-Hasser; 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;

3
2017-09-08 23:17



Sie können dazu den std :: count oder std :: count_if verwenden. Unterhalb eines einfachen Beispiels mit std :: count:

//Count the number of words on string
#include <iostream>
#include <string>
#include <algorithm> //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;
}

2
2018-06-28 05:00



Eine O (N) -Lösung, die auch sehr einfach zu verstehen und zu implementieren ist:

(Ich habe nicht nach einer leeren Zeichenfolge Eingabe überprüft. Aber ich bin sicher, dass Sie das leicht tun können.)

#include <iostream>
#include <string>
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 : "<<numberOfWords<<endl;

    return 0;
}

1
2018-03-01 18:05



Ein sehr prägnanter O (N) Ansatz:

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

Ein Teil-und-herrsche Ansatz, Komplexität ist auch 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);
}

0
2018-04-30 19:29



Ein Single-Pass-Algorithmus für dieses Problem kann der folgende sein:

  1. Wenn die Zeichenfolge leer ist, geben Sie 1 zurück
  2. Lassen Sie Übergänge = Anzahl der benachbarten Char-Paare (c1, c2) wo c1 == ' ' und c2 != ' '
  3. Wenn der Satz mit einem Leerzeichen beginnt, kehren Sie zurück transitions sonst zurück transitions + 1

Hier ist ein Beispiel mit string = "Ein sehr, sehr, sehr, sehr, sehr großer Hund hat meine Hausaufgaben gegessen !!!!"

 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!!!!
   |  x     x     x     x     x    x   x   x   x  x

Erläuterung

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

Dieser Algorithmus behandelt die Fälle mit mehreren Leerzeichen ordnungsgemäß

Hier sind zwei Lösungen, die ich mir ausgedacht habe

Naive Lösung

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

Wenn Sie genau überlegen, werden Sie in der Lage sein, diese Reihe von Operationen in ein inneres Produkt zu reduzieren, was im Folgenden getan wurde.

Innenproduktlösung

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

0
2018-06-27 01:13