Pankaj Tanwar
Published on

Number of Valid Words in a Sentence.

––– views

Problem of the day - Number of Valid Words in a Sentence

Tag - Easy

A sentence consists of lowercase letters ('a' to 'z'), digits ('0' to '9'), hyphens ('-'), punctuation marks ('!', '.', and ','), and spaces (' ') only. Each sentence can be broken down into one or more tokens separated by one or more spaces ' '.

A token is a valid word if:

  • It only contains lowercase letters, hyphens, and/or punctuation (no digits).
  • There is at most one hyphen '-'. If present, it should be surrounded by lowercase characters ("a-b" is valid, but "-ab" and "ab-" are not valid).
  • There is at most one punctuation mark. If present, it should be at the end of the token.

Examples of valid words include "a-b.", "afad", "ba-c", "a!", and "!".

Given a string sentence, return the number of valid words in sentence.

Example 1:

Input: sentence = "cat and dog" Output: 3 Explanation: The valid words in the sentence are "cat", "and", and "dog".

I appeared for leetcode contest today. This question was the first problem of it. The problem seemed very tricky at first glance.

After scratching my head for some time, I was able to come up with a approach.

My Algorithm

A word would be valid only if -

  • It doesn't contain any digit
  • Total punctuation in the word should be less than equal to 1.
  • If number of punctuation is 1, it must be at the end of the word only
  • Total hypens in the word should be less than equal to 1
  • if number of hypens is 1, It must be either at the end of word or second last of the word (in case of last char is punctuation)

Here is my code

class Solution {
public:
    int countValidWords(string sentence) {
        int res = 0;
        int is_digits = 0;
        int hypens = 0;
        int dots = 0;
        int start = -1;


        for(int i=0;i<sentence.length();i++) {
            char c = sentence[i];
            if(c - '0' >= 0 && c - '0' <= 9) is_digits++;
            if(c == '-') hypens++;
            if(c == '.' || c == '!' || c == ',') dots++;


            if(c == ' ') {
                if(i-1 >= 0 && sentence[i-1] != ' ' && is_digits == 0 && hypens <= 1 && dots <= 1) {
                    if(dots == 0 || (dots == 1 && (sentence[i-1] == '.' || sentence[i-1] == '!' || sentence[i-1] == ','))) {
                        if(hypens == 0 || (hypens == 1 && (sentence[start] != '-' && (dots == 1 ? (i-2 >= 0 && sentence[i-2] != '-') : sentence[i-1] != '-')))) {
                            res++;
                        }
                    }
                }
                is_digits = 0;
                hypens = 0;
                dots = 0;
                start = -1;
                //cout << res << endl;
            } else {
               if(start == -1) start = i;
            }
        }
        // end check
        int i = sentence.length();
        if(i-1 >= 0 && sentence[i-1] != ' ' && is_digits == 0 && hypens <= 1 && dots <= 1) {
            if(dots == 0 || (dots == 1 && (sentence[i-1] == '.' || sentence[i-1] == '!' || sentence[i-1] == ','))) {
                if(hypens == 0 || (hypens == 1 && (sentence[start] != '-' && (dots == 1 ? (i-2 >= 0 && sentence[i-2] != '-') : sentence[i-1] != '-')))) {
                    res++;
                }
            }
        }
        return res;
    }
};

If you feel, I am missing on something, feel free to reach out to me

I welcome your suggestions to improve it further!

Thanks for being part of my daily-code-workout journey. As always, if you have any thoughts about anything shared above, don't hesitate to reach out.

You might like previous editions of my coding diary

Tweet this article