Regular Expression Matching

Source

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).
The function prototype should be:
bool isMatch(const char *s, const char *p)
Some examples:
isMatch(“aa”,”a”) → false
isMatch(“aa”,”aa”) → true
isMatch(“aaa”,”aa”) → false
isMatch(“aa”, “a*”) → true
isMatch(“aa”, “.*”) → true
isMatch(“ab”, “.*”) → true
isMatch(“aab”, “c*a*b”) → true

Online Judge
This problem is available at Online Judge. Head over there and it will judge your solution. Currently only able to compile C++/Java code. If you are using other languages, you can still verify your solution by looking at the judge’s test cases and its expected output.
Background:
This interesting problem has been asked in Facebook and Google interviews. It might seem deceptively easy even you know the general idea, but programming it correctly with all the details require careful thought.
Edit:
It seems that some readers are confused about why the regex pattern “.*” matches the string “ab”. “.*” means repeat the preceding element 0 or more times. Here, the “preceding” element is the dot character in the pattern, which can match any characters. Therefore, the regex pattern “.*” allows the dot to be repeated any number of times, which matches any string (even an empty string).
Hints:
Think carefully how you would do matching of ‘*’. Please note that ‘*’ in regular expression is different from wildcard matching, as we match the previous character 0 or more times. But, how many times? If you are stuck, recursion is your friend.
This problem is a tricky one. Due to the huge number of edge cases, many people would write lengthy code and have numerous bugs on their first try. Try your best getting your code correct first, then refactor mercilessly to as clean and concise as possible!

A sample diagram of a deterministic finite state automata (DFA). DFAs are useful for doing lexical analysis and pattern matching. An example is UNIX’s grep tool. Please note that this post does not attempt to descibe a solution using DFA.

Solution:
This looks just like a straight forward string matching, isn’t it? Couldn’t we just match the pattern and the input string character by character? The question is, how to match a ‘*’?
A natural way is to use a greedy approach; that is, we attempt to match the previous character as many as we can. Does this work? Let us look at some examples.
s = “abbbc”, p = “ab*c”
Assume we have matched the first ‘a’ on both s and p. When we see “b*” in p, we skip all b’s in s. Since the last ‘c’ matches on both side, they both match.
s = “ac”, p = “ab*c”
After the first ‘a’, we see that there is no b’s to skip for “b*”. We match the last ‘c’ on both side and conclude that they both match.
It seems that being greedy is good. But how about this case?
s = “abbc”, p = “ab*bbc”
When we see “b*” in p, we would have skip all b’s in s. They both should match, but we have no more b’s to match. Therefore, the greedy approach fails in the above case.
One might be tempted to think of a quick workaround. How about counting the number of consecutive b’s in s? If it is smaller or equal to the number of consecutive b’s after “b*” in p, we conclude they both match and continue from there. For the opposite, we conclude there is not a match.
This seem to solve the above problem, but how about this case:
s = “abcbcd”, p = “a.*c.*d”
Here, “.*” in p means repeat ‘.’ 0 or more times. Since ‘.’ can match any character, it is not clear how many times ‘.’ should be repeated. Should the ‘c’ in p matches the first or second ‘c’ in s? Unfortunately, there is no way to tell without using some kind of exhaustive search.
We need some kind of backtracking mechanism such that when a matching fails, we return to the last successful matching state and attempt to match more characters in s with ‘*’. This approach leads naturally to recursion.
The recursion mainly breaks down elegantly to the following two cases:

1. If the next character of p is NOT ‘*’, then it must match the current character of s. Continue pattern matching with the next character of both s and p.
2. If the next character of p is ‘*’, then we do a brute force exhaustive matching of 0, 1, or more repeats of current character of p… Until we could not match any more characters.

You would need to consider the base case carefully too. That would be left as an exercise to the reader.
Below is the extremely concise code (Excluding comments and asserts, it’s about 10 lines of code).

bool isMatch(const char *s, const char *p) {   assert(s && p);   if (*p == '\0') return *s == '\0';     // next char is not '*': must match current character   if (*(p+1) != '*') {     assert(*p != '*');     return ((*p == *s) || (*p == '.' && *s != '\0')) && isMatch(s+1, p+1);   }   // next char is '*'   while ((*p == *s) || (*p == '.' && *s != '\0')) {     if (isMatch(s, p+2)) return true;     s++;   }   return isMatch(s, p+2); }

Further Thoughts:
Some extra exercises to this problem:

1. If you think carefully, you can exploit some cases that the above code runs in exponential complexity. Could you think of some examples? How would you make the above code more efficient?
2. Try to implement partial matching instead of full matching. In addition, add ‘^’ and ‘$’ to the rule. ‘^’ matches the starting position within the string, while ‘$’ matches the ending position of the string.
3. Try to implement wildcard matching where ‘*’ means any sequence of zero or more characters.

For the interested reader, real world regular expression matching (such as the grep tool) are usually implemented by applying formal language theory. To understand more about it, you may read this article.

Find the repeating and the missing in an unsorted array

Source

Given an unsorted array of size n. Array elements are in range from 1 to n. One number from set {1, 2, …n} is missing and one number occurs twice in array. Find these two numbers.

Examples:

  arr[] = {3, 1, 3}   Output: 2, 3   // 2 is missing and 3 occurs twice     arr[] = {4, 3, 6, 2, 1, 1}   Output: 1, 5  // 5 is missing and 1 occurs twice 

Method 1 (Use Sorting)
1) Sort the input array.
2) Traverse the array and check for missing and repeating.

Time Complexity: O(nLogn)

Thanks to LoneShadow for suggesting this method.

Method 2 (Use count array)
1) Create a temp array temp[] of size n with all initial values as 0.
2) Traverse the input array arr[], and do following for each arr[i]
……a) if(temp[arr[i]] == 0) temp[arr[i]] = 1;
……b) if(temp[arr[i]] == 1) output “arr[i]” //repeating
3) Traverse temp[] and output the array element having value as 0 (This is the missing element)

Time Complexity: O(n)
Auxiliary Space: O(n)

Method 3 (Use elements as Index and mark the visited places)
Traverse the array. While traversing, use absolute value of every element as index and make the value at this index as negative to mark it visited. If something is already marked negative then this is the repeating element. To find missing, traverse the array again and look for a positive value.

?

#include #include void printTwoElements(int arr[], int size) { int i; printf("\n The repeating element is"); for(i = 0; i < size; i++) { if(arr[abs(arr[i])-1] > 0) arr[abs(arr[i])-1] = -arr[abs(arr[i])-1]; else printf(" %d ", abs(arr[i])); } printf("\nand the missing element is "); for(i=0; i { if(arr[i]>0) printf("%d",i+1); } } /* Driver program to test above function */ int main() { int arr[] = {7, 3, 4, 5, 5, 6, 2}; int n = sizeof(arr)/sizeof(arr[0]); printTwoElements(arr, n); return 0; }

Time Complexity: O(n)

Thanks to Manish Mishra for suggesting this method.

Method 4 (Make two equations)
Let x be the missing and y be the repeating element.

1) Get sum of all numbers.
Sum of array computed S = n(n+1)/2 – x + y
2) Get product of all numbers.
Product of array computed P = 1*2*3*…*n * y / x
3) The above two steps give us two equations, we can solve the equations and get the values of x and y.

Time Complexity: O(n)

Thanks to disappearedng for suggesting this solution.

This method can cause arithmetic overflow as we calculate product and sum of all array elements. See this for changes suggested by john to reduce the chances of overflow.

Method 5 (Use XOR)
Let x and y be the desired output elements.
Calculate XOR of all the array elements.

     xor1 = arr[0]^arr[1]^arr[2].....arr[n-1]

XOR the result with all numbers from 1 to n

     xor1 = xor1^1^2^.....^n

In the result xor1, all elements would nullify each other except x and y. All the bits that are set in xor1 will be set in either x or y. So if we take any set bit (We have chosen the rightmost set bit in code) of xor1 and divide the elements of the array in two sets – one set of elements with same bit set and other set with same bit not set. By doing so, we will get x in one set and y in another set. Now if we do XOR of all the elements in first set, we will get x, and by doing same in other set we will get y.

?

#include #include /* The output of this function is stored at *x and *y */ void getTwoElements(int arr[], int n, int *x, int *y) { int xor1; /* Will hold xor of all elements and numbers from 1 to n */ int set_bit_no; /* Will have only single set bit of xor1 */ int i; *x = 0; *y = 0; xor1 = arr[0]; /* Get the xor of all array elements elements */ for(i = 1; i < n; i++) xor1 = xor1^arr[i]; /* XOR the previous result with numbers from 1 to n*/ for(i = 1; i <= n; i++) xor1 = xor1^i; /* Get the rightmost set bit in set_bit_no */ set_bit_no = xor1 & ~(xor1-1); /* Now divide elements in two sets by comparing rightmost set bit of xor1 with bit at same position in each element. Also, get XORs of two sets. The two XORs are the output elements. The following two for loops serve the purpose */ for(i = 0; i < n; i++) { if(arr[i] & set_bit_no) *x = *x ^ arr[i]; /* arr[i] belongs to first set */ else *y = *y ^ arr[i]; /* arr[i] belongs to second set*/ } for(i = 1; i <= n; i++) { if(i & set_bit_no) *x = *x ^ i; /* i belongs to first set */ else *y = *y ^ i; /* i belongs to second set*/ } /* Now *x and *y hold the desired output elements */ } /* Driver program to test above function */ int main() { int arr[] = {1, 3, 4, 5, 5, 6, 2}; int *x = (int *)malloc(sizeof(int)); int *y = (int *)malloc(sizeof(int)); int n = sizeof(arr)/sizeof(arr[0]); getTwoElements(arr, n, x, y); printf(" The two elements are %d and %d", *x, *y); getchar(); }

Time Complexity: O(n)

Calculate Logn in one line

Source

Write a one line C function that calculates and returns . For example, if n = 64, then your function should return 6, and if n = 129, then your function should return 7.

Following is a solution using recursion.

?

#include unsigned int Log2n(unsigned int n) { return (n > 1)? 1 + Log2n(n/2): 0; } int main() { unsigned int n = 32; printf("%u", Log2n(n)); getchar(); return 0; }

Let us try an extended verision of the problem. Write a one line function Logn(n ,r) which returns . Following is the solution for the extended problem.

?

#include unsigned int Logn(unsigned int n, unsigned int r) { return (n > r-1)? 1 + Logn(n/r, r): 0; } int main() { unsigned int n = 256; unsigned int r = 4; printf("%u", Logn(n, r)); getchar(); return 0; }