leetcode 10. Regular Expression Matching

leetcode
九章

题目描述

Given an input string (s) and a pattern (p), implement regular expression
matching with support for '.' and '*'.
‘.’ Matches any single character. ‘*’ Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

Note:

  • s could be empty and contains only lowercase letters a-z.
  • p could be empty and contains only lowercase letters a-z, and characters like . or *.

Example 1:
Input: s = “aa” p = “a” Output: false Explanation: “a” does not match the entire string “aa”.

Example 2:
Input: s = “aa” p = “a*” Output: true Explanation: ‘*’ means zero or more of the preceding element, ‘a’. Therefore, by repeating ‘a’ once, it becomes “aa”.

Example 3:
Input: s = “ab” p = “.*” Output: true Explanation: “.*” means “zero or more (*) of any character (.)”.

Example 4:
Input: s = “aab” p = “cab” Output: true Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore, it matches “aab”.

Example 5:
Input: s = “mississippi” p = “misis*p.” Output: false

Tags: String, Dynamic Programming, Backtracking

Difficulty: Hard

答案



leetcode 44. Wildcard Matching

leetcode
九章

题目描述

Given an input string (s) and a pattern (p), implement wildcard pattern
matching with support for '?' and '*'.

'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).

The matching should cover the entire input string (not partial).

Note:

  • s could be empty and contains only lowercase letters a-z.
  • p could be empty and contains only lowercase letters a-z, and characters like ? or *.

Example 1:

Input:
s = "aa"
p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".

Example 2:

Input:
s = "aa"
p = "*"
Output: true
Explanation:  '*' matches any sequence.

Example 3:

Input:
s = "cb"
p = "?a"
Output: false
Explanation:  '?' matches 'c', but the second letter is 'a', which does not match 'b'.

Example 4:

Input:
s = "adceb"
p = "*a*b"
Output: true
Explanation:  The first '*' matches the empty sequence, while the second '*' matches the substring "dce".

Example 5:

Input:
s = "acdcb"
p = "a*c?b"
Output: false

Tags: String, Dynamic Programming, Backtracking, Greedy

Difficulty: Hard

答案



leetcode 79. Word Search

难度:Middle

leetcode
九章

题目描述

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where
“adjacent” cells are those horizontally or vertically neighboring. The same
letter cell may not be used more than once.

Example:

board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

Given word = " **ABCCED** ", return **true**.
Given word = " **SEE** ", return **true**.
Given word = " **ABCB** ", return **false**.

Tags: Array, Backtracking

Difficulty: Medium

答案

leetcode 78. Subsets

难度:Middle

leetcode
九章

题目描述

Given a set of distinct integers, nums , return all possible subsets
(the power set).

Note: The solution set must not contain duplicate subsets.

Example:

Input: nums = [1,2,3]
Output:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

Tags: Array, Backtracking, Bit Manipulation

Difficulty: Medium

答案

leetcode 39. Combination Sum

难度:Middle

leetcode
九章

题目描述

Given a set of candidate numbers (candidates) (without duplicates)
and a target number (target), find all unique combinations in candidates
where the candidate numbers sums to target.

The same repeated number may be chosen from candidates unlimited number
of times.

Note:

  • All numbers (including target) will be positive integers.
  • The solution set must not contain duplicate combinations.

Example 1:

Input: candidates = [2,3,6,7], target = 7,
**A solution set is:**
[
  [7],
  [2,2,3]
]

Example 2:

Input: candidates = [2,3,5], target = 8,
**A solution set is:**
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]

Tags: Array, Backtracking

Difficulty: Medium

答案


:D 一言句子获取中...