count the words in a string

count_words.cpp

// ====================== a good concise version ===================== 4/30/2014 ==
// ================================================================================

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

// ====================== a Divide-and-Conquer version ============== 4/30/2014 ==
// ===============================================================================


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



// ====================== a bad version =================================
// ======================================================================

bool is_letter(char c) {
    return 'a' <= c && c <= 'z' || 'A' <= c && c <= 'Z';   
}
int count_words(const char* s) {
		if(!s || *s == '\0') return 0;
		int count = 0, i = 0, len = strlen(s);
		while(s[i] == ' ') i++;
		if(i == len) return 0;
		bool wordbegin = false;
		while(i < len) {
			if(is_letter(s[i])) {
				if(!wordbegin) {
						wordbegin = true;
						count++;
				}
				i++;
			}
			else {
				wordbegin = false;
				while(s[i] == ' ' && i<len) i++;
			}
		}
		return count;
}