Wildcard Matching

Problem: 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).

Approach: Use DP

        public bool IsWildCardMatch(string s, string p)

        {

            bool[,] lookup = new bool[s.Length + 1, p.Length + 1];

            lookup[0, 0] = true;

            for (int i = 1; i <= p.Length; ++i)

            {

                if (p[i - 1] == '*')

                {

                    lookup[0, i] = lookup[0, i - 1];

                }

            }

            for (int i = 1; i <= s.Length; ++i)

            {

                for (int j = 1; j <= p.Length; ++j)

                {

                    if (p[j - 1] == '*')

                    {

                        lookup[i, j] = lookup[i, j - 1] || lookup[i - 1, j];

                    }

                    else if (p[j -1] == '?' || s[i - 1] == p[j - 1])

                    {

                        lookup[i, j] = lookup[i - 1, j - 1];

                    }

                    else

                    {

                        lookup[i, j] = false;

                    }

                }

            }

            return lookup[s.Length, p.Length];

        }

[AirBnb] Combination Sum

Problem: 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.

Example:

Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Explanation:
2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times.
7 is a candidate, and 7 = 7.
These are the only two combinations.

Approach: Use backtracking.

Implementation in C#:

        public IList<IList<int>> CombinationSum(int[] candidates, int target)

        {

            IList<IList<int>> result = new List<IList<int>>();

            if (candidates == null || candidates.Length == 0)

            {

                return result;

            }

            Array.Sort(candidates);

            List<int> currResult = new List<int>();

            this.FindCombinationSumCandidates(candidates, target, result, currResult, 0);

            return result;

        }

        private void FindCombinationSumCandidates(int[] candidates, int target, IList<IList<int>> result, List<int> currResult, int currIndex)

        {

            if (target < 0)

            {

                return;

            }

            if (target == 0)

            {

                result.Add(new List<int>(currResult));

                return;

            }

            while(currIndex < candidates.Length && target - candidates[currIndex] >= 0)

            {

                currResult.Add(candidates[currIndex]);

                this.FindCombinationSumCandidates(candidates, target - candidates[currIndex], result, currResult, currIndex);

                ++currIndex;

                currResult.RemoveAt(currResult.Count - 1);

            }

        }

Complexity: O(2 ^ k) where k is is the sum of target / candidates[i] for all i = 0 to length of candidates.

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

 Approach: Use binary search 

        public int SearchInsert(int[] nums, int target)

        {

            if (nums == null)

            {

                return -1;

            }

            if (nums.Length == 0 || target < nums[0])

            {

                return 0;

            }

            else if (target > nums[nums.Length - 1])

            {

                return nums.Length;

            }

            return this.SearchInsert(nums, 0, nums.Length - 1, target);

        }

        private int SearchInsert(int[] nums, int low, int high, int target)

        {

            if (low > high)

            {

                return -1;

            }

            int mid = (low + high) / 2;

            if (nums[mid] == target || (nums[mid] > target && nums[mid - 1] < target))

            {

                return mid;

            }

            else if (nums[mid] < target)

            {

                return this.SearchInsert(nums, mid + 1, high, target);

            }

            else

            {

                return this.SearchInsert(nums, low, mid - 1, target);

            }

        }

Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.

 Approach: Use binary search

        public int[] SearchRange(int[] nums, int target)

        {

            if (nums == null || nums.Length <= 0)

            {

                return new int[] { -1, -1 };

            }

            if (nums.Length == 1)

            {

                return nums[0] == target ? new int[] { 0, 0 } : new int[] { -1, -1 };

            }

            int first = this.GetFirstOccurance(nums, 0, nums.Length - 1, target);

            if (first == -1)

            {

                return new int[] { -1, -1 };

            }

            int last = this.GetLastOccurance(nums, 0, nums.Length - 1, target);

            return new int[] { first, last };

        }

        private int GetFirstOccurance(int[] nums, int low, int high, int target)

        {

            if (low > high)

            {

                return -1;

            }

            int mid = (low + high) / 2;

            if ((nums[mid] == target) && (mid == 0 || nums[mid] > nums[mid - 1]))

            {

                return mid;

            }

            else if (nums[mid] < target)

            {

                return this.GetFirstOccurance(nums, mid + 1, high, target);

            }

            else

            {

                return this.GetFirstOccurance(nums, low, mid - 1, target);

            }

        }

        private int GetLastOccurance(int[] nums, int low, int high, int target)

        {

            if (low > high)

            {

                return -1;

            }

            int mid = (low + high) / 2;

            if ((nums[mid] == target) && (mid == nums.Length - 1 || nums[mid] < nums[mid + 1]))

            {

                return mid;

            }

            else if (nums[mid] > target)

            {

                return this.GetLastOccurance(nums, low, mid - 1, target);

            }

            else

            {

                return this.GetLastOccurance(nums, mid + 1, high, target);

            }

        }

Longest Valid Parentheses

Problem: Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

Solution:

        public static int LongestValidParentheses(string s)

        {

            Stack<int> stack = new Stack<int>();

            stack.Push(-1);

            int result = 0;

            for(int i = 0; i < s.Length; ++i)

            {

                if (s[i] == '(')

                {

                    stack.Push(i);

                }

                else

                {

                    stack.Pop();

                    if (stack.Count > 0)

                    {

                        result = Math.Max(result, i - stack.Peek());

                    }

                    else

                    {

                        stack.Push(i);

                    }

                }

            }

            return result;

        }

[Microsoft][LeetCode] Next Permutation

Problem: A permutation of an array of integers is an arrangement of its members into a sequence or linear order.

• For example, for arr = [1,2,3], the following are all the permutations of arr: [1,2,3], [1,3,2], [2, 1, 3], [2, 3, 1], [3,1,2], [3,2,1].

The next permutation of an array of integers is the next lexicographically greater permutation of its integer. More formally, if all the permutations of the array are sorted in one container according to their lexicographical order, then the next permutation of that array is the permutation that follows it in the sorted container. If such arrangement is not possible, the array must be rearranged as the lowest possible order (i.e., sorted in ascending order).

• For example, the next permutation of arr = [1,2,3] is [1,3,2].
• Similarly, the next permutation of arr = [2,3,1] is [3,1,2].
• While the next permutation of arr = [3,2,1] is [1,2,3] because [3,2,1] does not have a lexicographical larger rearrangement.

Given an array of integers nums, find the next permutation of nums.

The replacement must be in place and use only constant extra memory.

Example:

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

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

Input: nums = [1,1,5]
Output: [1,5,1]

Approach: The approach which we are using here is mention on wikipedia. Here are the steps:

• Find the first number which is not in descending order. say at index i
• Find the number which is just bigger than the number found at step 1. Say at index j. Swap arr[i] and arr[j].
• Reverse the array from i + 1 to array's length.

Implementation in C#:

    public void NextPermutation(int[] nums)

    {

        int length = nums?.Length ?? 0;

        if (length <= 1)

        {

            return;

        }

        int i = length - 1;

        while (i > 0 && nums[i] <= nums[i - 1])

        {

            i--;

        }

        if (i > 0)

        {

            int j = length - 1;

            while (j > i - 1 && nums[i - 1] >= nums[j])

            {

                --j;

            }

            this.Swap(nums, i - 1, j);

        }

        this.Reverse(nums, i);

    }

    private void Swap(int[] nums, int i, int j)

    {

        int temp = nums[i];

        nums[i] = nums[j];

        nums[j] = temp;

    }

    private void Reverse(int[] nums, int start)

    {

        int end = nums.Length - 1;

        while (start < end)

        {

            this.Swap(nums, start++, end--);

        }

    }

Complexity: O(n)

You are given a string s and an array of strings words of the same length. Return all starting indices of substring(s) in s that is a concatenation of each word in words exactly once, in any order, and without any intervening characters.

 Approach: Use hash

        public IList<int> FindSubstringWithConcatenation(string s, string[] words)

        {

            List<int> result = new List<int>();

            int numOfWords = words.Length;

            int sizeOfWord = words[0].Length;

            int sizeOfWords = sizeOfWord * numOfWords;

            if (s.Length < sizeOfWords)

            {

                return result;

            }

            Dictionary<string, int> hash = new Dictionary<string, int>();

            foreach(string word in words)

            {

                if (hash.ContainsKey(word))

                {

                    ++hash[word];

                }

                else

                {

                    hash[word] = 1;

                }

            }

            for (int i = 0; i <= s.Length - sizeOfWords; ++i)

            {

                Dictionary<string, int> tempHash = new Dictionary<string, int>(hash);

                int count = numOfWords;

                for(int j = i; j < i + sizeOfWords; j+= sizeOfWord)

                {

                    string str = s.Substring(j, sizeOfWord);

                    if (!tempHash.ContainsKey(str) || tempHash[str] == 0)

                    {

                        break;

                    }

                    --tempHash[str];

                    --count;

                }

                if(count == 0)

                {

                    result.Add(i);

                }

            }

            return result;

        }