Skip to main content

Wildcard Character match


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

Solution- 


Comments

Post a Comment

Popular posts from this blog

Java 8- Sorting a hashmap (by key and by value) using lambda expression and streams

Sometimes while working on business problems, it’s very common to come across use cases wherein a map needs to be sorted by either keys or by values. In this post, we will cover some of the examples to sort a map of primitives and custom objects.   In below approaches, we will not destroy existing map and will create a new map to ensure consistency of sorting 1. Sort HashMap by key  In order to sort a map by key, all we need to do is to use sorted method of stream interface and pass a default default/custom comparator to it. Moreover, to sort by keys, we need to use comparingByKey method of Entry interface of Map. 2. Sort HashMap by values  In order to sort a map by key, all we need to do is to use sorted method of stream interface and pass a default default/custom comparator to it. Moreover, to sort by keys, we need to use comparingByValue method of Entry interface of Map.
Post a Comment
Read more

Walls and gates- Find shortest distances between rooms and gates

Leetcode: Walls and Gates You are given a  m x n  2D grid initialized with these three possible values. -1  - A wall or an obstacle. 0  - A gate. INF  - Infinity means an empty room. We use the value  2 31  - 1 = 2147483647  to represent  INF  as you may assume that the distance to a gate is less than 2147483647 . Fill each empty room with the distance to its  nearest  gate. If it is impossible to reach a gate, it should be filled with  INF . For example, given the 2D grid: INF -1 0 INF INF INF INF -1 INF -1 INF -1 0 -1 INF INF After running your function, the 2D grid should be: 3 -1 0 1 2 2 1 -1 1 -1 2 -1 0 -1 3 4 Understand the problem: It is very classic backtracking problem. We can start from each gate (0 point), and searching for its neighbors. We can either use DFS or BFS solution. Below is a DFS solution-
Post a Comment
Read more

Design LRU Cache

Design and implement a data structure for  Least Recently Used (LRU) cache . It should support the following operations:  get  and  put . get(key)  - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1. put(key, value)  - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item. Follow up: Could you do both operations in  O(1)  time complexity? Example: LRUCache cache = new LRUCache( 2 /* capacity */ ); cache.put(1, 1); cache.put(2, 2); cache.get(1);        // returns 1 cache.put(3, 3);      // evicts key 2 cache.get(2);        // returns -1 (not found) cache.put(4, 4);     // evicts key 1 cache.get(1);        //...
Post a Comment
Read more