“This is the 10th day of my participation in the First Challenge 2022. For details: First Challenge 2022”

Topic describes

This is 2047 on LeetCode. The number of effective words in the sentence is easy.

Tag: “analog”, “dual pointer”

Sentences consist only of lowercase letters (‘a’ to ‘z’), numbers (‘0’ to ‘9’), hyphens (‘-‘), punctuation marks (‘! ‘,’.’ and ‘,’) and Spaces (‘ ‘). Each sentence can be broken down into one or more tokens based on Spaces, separated by one or more Spaces.

A token is considered a valid word if it meets both of the following conditions:

  • Use only lowercase letters, hyphens, and/or punctuation (no numbers).
  • One hyphen at mostThe '-'. If so, there should be lowercase letters on both sides of the hyphen ("a-b"Is a valid word, but"-ab" 和 "ab-"Not a valid word.
  • One punctuation mark at most. If present, punctuation should be locatedtokenAt the end.

Here are some examples of words that work: “a-b.”, “afad”, “ba-c”, “A!” And “!” .

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

Example 1:

Enter: sentence = "cat and dog" Output: 3 Explanation: The valid words in this sentence are "cat", "and" and" dog"Copy the code

Example 2:

Enter: sentence = "! this 1-s b8d!" Output: 0 Explanation: There are no valid words in the sentence! "This" is not a valid word because it begins with a punctuation mark. "1-s" and "b8d" are also not valid words because they both contain numbersCopy the code

Example 3:

Sentence = "Alice and Bob are playing stone-game10" The valid words in this sentence are" Alice ", "and", "Bob", "are" and" playing". "stone-game10" is not a valid word because it contains numbersCopy the code

Example 4:

Enter: sentence = "He bought 2 pencils, 3 erasers, and 1 pencil-sharpener." The valid words in this sentence are "he"," bought"," Pencils," "erasers," "and" and" pencil-sharpener."Copy the code

Tip:


  • 1 < = s e n t e n c e . l e n g t h < = 1000 1 <= sentence.length <= 1000
  • sentenceConsists of lowercase letters, digits (0-9), and characters (' ',The '-','! ','. 'And ‘,’)
  • At least in the sentence
    1 1     个 token

simulation

Simulate the sentence according to the meaning of the question. Firstly, divide sentence according to the space to obtain multiple items, then check the validity of each item, and finally count the number of legitimate items as the answer.

When checking the validity of item, C1C1C1 and C2C2C2 are used to represent the occurrence times of “hyphen” and “punctuation” respectively.

Note: Java’s split operation is rege-based and linear in complexity. Other languages may need to use a “two-pointer” hand-written split operation

The code (see P2P2P2 for the double pointer to split) :

class Solution {
    public int countValidWords(String sentence) {
        String[] ss = sentence.split("");
        int ans = 0;
        for (String s : ss) if (check(s)) ans++;
        return ans;
    }
    boolean check(String s) {
        int n = s.length();
        if (n == 0) return false;
        for (int i = 0, c1 = 0, c2 = 0; i < n; i++) {
            char c = s.charAt(i);
            if (Character.isDigit(c)) return false;
            if (c == ' ') return false;
            if (c == The '-' && ++c1 >= 0) {
                if (c1 > 1 || (i == 0 || i == n - 1)) return false;
                if(! Character.isLetter(s.charAt(i -1)) || !Character.isLetter(s.charAt(i + 1))) return false;
            }
            if ((c == '! ' || c == '. ' || c == ', ') && ++c2 >= 0) {
                if (c2 > 1|| (i ! = n -1)) return false; }}return true; }}Copy the code
class Solution {
    public int countValidWords(String sentence) {
        int n = sentence.length(), ans = 0;
        for (int i = 0; i < n; ) {
            if (sentence.charAt(i) == ' ' && ++i >= 0) continue;
            int j = i;
            while(j < n && sentence.charAt(j) ! =' ') j++;
            if (check(sentence.substring(i, j))) ans++;
            i = j + 1;
        }
        return ans;
    }
    boolean check(String s) {
        int n = s.length();
        if (n == 0) return false;
        for (int i = 0, c1 = 0, c2 = 0; i < n; i++) {
            char c = s.charAt(i);
            if (Character.isDigit(c)) return false;
            if (c == ' ') return false;
            if (c == The '-' && ++c1 >= 0) {
                if (c1 > 1 || (i == 0 || i == n - 1)) return false;
                if(! Character.isLetter(s.charAt(i -1)) || !Character.isLetter(s.charAt(i + 1))) return false;
            }
            if ((c == '! ' || c == '. ' || c == ', ') && ++c2 >= 0) {
                if (c2 > 1|| (i ! = n -1)) return false; }}return true; }}Copy the code
  • Time complexity: O(n)O(n)O(n)
  • Spatial complexity: the execution process will generate a number of substrings, the total length of substrings andsThe same. Complexity of
    O ( n ) O(n)

The last

This is the No.2047 of our “Brush through LeetCode” series of articles. The series started on 2021/01/01.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour… .

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.