A simple sentence if syntactically correct if it fulfills given rules. The following are given rules.
1. Sentence must start with a Uppercase character (e.g. Noun/ I/ We/ He etc.)
2. Then lowercase character follows.
3. There must be spaces between words.
4. Then the sentence must end with a full stop(.) after a word.
5. Two continuous spaces are not allowed.
6. Two continuous upper case characters are not allowed.
7. However the sentence can end after an upper case character.
Correct sentences - "My name is Ram." "The vertex is S." "I am single." "I love Geeksquiz and Geeksforgeeks." Incorrect sentence - "My name is KG." "I lovE cinema." "GeeksQuiz. is a quiz site." " You are my friend." "I love cinema"
Question: Given a sentence, validate the given sentence for above given rules.
We strongly recommend to minimize the browser and try this yourself first.
The idea is to use an automata for the given set of rules.
1. Check for the corner cases
…..1.a) Check if the first character is uppercase or not in the sentence.
…..1.b) Check if the last character is a full stop or not.
2. For rest of the string, this problem could be solved by following a state diagram. Please refer to the below state diagram for that.
3. We need to maintain previous and current state of different characters in the string. Based on that we can always validate the sentence of every character traversed.
A C based implementation is below. (By the way this sentence is also correct according to the rule and code)
"I love cinema." is correct "The vertex is S." is correct "I am single." is correct "My name is KG." is incorrect "I lovE cinema." is incorrect "GeeksQuiz. is a quiz site." is incorrect "I love Geeksquiz and Geeksforgeeks." is correct " You are my friend." is incorrect "I love cinema" is incorrect
Time complexity – O(n), worst case as we have to traverse the full sentence where n is the length of the sentence.
Auxiliary space – O(1)