Sunday, February 1, 2015

Regular expression implementation for '*' and '?' wildcard characters

Assuming we have two string - a normal string which will be matched against a regular expression string. The idea is simple: iterate through both string simultaneously. If:

  • current char in regex is '?', skip current characters from both strings
  • current char in regex is '*', find the next matching character in original string
  • else match the current character.

The implementation of the above idea is captured in code at the link

Sliding window implementation:

Problem: Given an array and subarray size, find the max. sum from subarrays.
Solution: 
Naive solution is to iterate through all the subarrays and find the sums. Each time, compare the sum with the previous max and update accordingly. The solution is quadratic in nature.
A better solution implementing sliding window where in each iteration, remove the first integer in the last array and add the value of the newly added array in the subarray.
An implementation of it is here in the link.