Press "Enter" to skip to content

Posts tagged as “match”

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

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


  • 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)


Solution 2: Regex

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


花花酱 LeetCode 1367. Linked List in Binary Tree

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.


  • 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|)