match Archives - Huahua's Tech Road

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".

Example 2:

Input: sentence = "!this  1-s b8d!"
Output: 0
Explanation: There are no valid words in the sentence.
"!this" is invalid because it starts with a punctuation mark.
"1-s" and "b8d" are invalid because they contain digits.

Example 3:

Input: sentence = "alice and  bob are playing stone-game10"
Output: 5
Explanation: The valid words in the sentence are "alice", "and", "bob", "are", and "playing".
"stone-game10" is invalid because it contains digits.

Example 4:

Input: sentence = "he bought 2 pencils, 3 erasers, and 1  pencil-sharpener."
Output: 6
Explanation: The valid words in the sentence are "he", "bought", "pencils,", "erasers,", "and", and "pencil-sharpener.".

Constraints:

1 <= sentence.length <= 1000
sentence only contains lowercase English letters, digits, ' ', '-', '!', '.', and ','.
There will be at least 1 token.

Solution 1: Brute Force

Time complexity: O(n)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int countValidWords(string sentence) {

stringstream ss(sentence);

string word;

int ans = 0;

while (ss >> word) {

bool valid = true;

int hyphen = 0;

int punctuation = 0;

char p = ' ';

for (char c : word) {

if (c == '-') {

if (++hyphen > 1 || !isalpha(p)) {

valid = false;

break;

}

} else if (c == '!' || c == '.' || c == ',') {

if (++punctuation > 1 || p == '-') {

valid = false;

break;

}

} else if (isalpha(c)) {

if (punctuation) {

valid = false;

break;

}

} else {

valid = false;

break;

}

p = c;

}

if (word.back() == '-')

valid = false;

if (valid) ++ans;

}

return ans;

}

};

Solution 2: Regex

Time complexity: O(n^2)?
Space complexity: O(1)

Python

# Author: Huahua

class Solution:

def countValidWords(self, sentence: str) -> int:

ans = 0

for word in sentence.split():

if word.strip() and re.fullmatch('^([a-z]+(-?[a-z]+)?)?[\.,!]?$', word.strip()):

ans += 1

return ans

Given a binary tree root and a linked list with head as the first node.

Return True if all the elements in the linked list starting from the head correspond to some downward path connected in the binary tree otherwise return False.

In this context downward path means a path that starts at some node and goes downwards.

Example 1:

Input: head = [4,2,8], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
Output: true
Explanation: Nodes in blue form a subpath in the binary Tree.

Example 2:

Input: head = [1,4,2,6], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
Output: true

Example 3:

Input: head = [1,4,2,6,8], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
Output: false
Explanation: There is no path in the binary tree that contains all the elements of the linked list from head.

Constraints:

1 <= node.val <= 100 for each node in the linked list and binary tree.
The given linked list will contain between 1 and 100 nodes.
The given binary tree will contain between 1 and 2500 nodes.

Solution: Recursion

We need two recursion functions: isSubPath / isPath, the later one does a strict match.

Time complexity: O(|L| * |T|)
Space complexity: O(|T|)

C++

class Solution {

public:

bool isSubPath(ListNode* head, TreeNode* root) {

if (!root) return false;

return isPath(head, root) || isSubPath(head, root->left) || isSubPath(head, root->right);

}

private:

bool isPath(ListNode* head, TreeNode* root) {

if (!head) return true;

if (!root) return false;

if (root->val != head->val) return false;

return isPath(head->next, root->left) || isPath(head->next, root->right);

}

};

Posts tagged as “match”

花花酱 LeetCode 2047. Number of Valid Words in a Sentence

Solution 1: Brute Force

C++

Solution 2: Regex

Python

Posts tagged as “match”

花花酱 LeetCode 2047. Number of Valid Words in a Sentence

Solution 1: Brute Force

C++

Solution 2: Regex

Python

花花酱 LeetCode 1367. Linked List in Binary Tree

Solution: Recursion

C++