Google Interview Question Software Engineers
Country: United States
Interview Type: In-Person
#include <iostream>
#include <string>
#include <stack>
#include <map>
#include <deque>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <sstream>
#include <vector>
#include <algorithm>
using namespace std;
typedef string::iterator iter;
bool reg(iter is, iter ie, iter rs, iter re){
if(is == ie && rs == re)
return true;
if(is == ie && rs != re){
if(*rs == '+') return reg(is,ie,++rs,re);
if(*rs == '*') return reg(is,ie,++rs,re);
return false;
}
if(is != ie && rs == re)
return false;
if(*rs == '+')
return reg(++is,ie,++rs,re);
if(*rs == '*'){
bool r;
rs++;
while(is != ie){
r |= reg(++is,ie,rs,re);
}
return r;
}
if(*is == *rs)
return reg(++is,ie,++rs,re);
if(*is != *rs)
return false;
}
//just a wrapper
bool isMatch(string s, string regx){
cout << "Checking " << s << " against " << regx << " ... ";
if(reg(s.begin(), s.end(), regx.begin(), regx.end())){
cout << "MATCH !" << endl;
return true;
}else{
cout << "no match found." <<endl;
return false;
}
}
int main(){
string text = "baaabab";
isMatch(text, "ba*a++");
isMatch(text, "ba*a+");
isMatch(text, "a*ab");
isMatch("","+");
}
Output:
Checking baaabab against ba*a++ ... MATCH !
Checking baaabab against ba*a+ ... MATCH !
Checking baaabab against a*ab ... no match found.
Checking against + ... MATCH !
...Program finished with exit code 0
Press ENTER to exit console.
#include <iostream>
#include <string>
using namespace std;
typedef string::iterator iter;
bool reg(iter is, iter ie, iter rs, iter re){
//cout << *is << " " << *rs << endl;
if(is == ie && rs == re)
return true;
if(is == ie && rs != re){
if(*rs == '+') return reg(is,ie,++rs,re);
if(*rs == '*') return reg(is,ie,++rs,re);
return false;
}
if(is != ie && rs == re)
return false;
if(*rs == '+')
return reg(++is,ie,++rs,re);
if(*rs == '*'){
bool r;
rs++;
while(is != ie){
r |= reg(++is,ie,rs,re);
}
return r;
}
if(*is == *rs)
return reg(++is,ie,++rs,re);
if(*is != *rs)
return false;
}
//wrapper
bool isMatch(string s, string regx){
cout << "Checking " << s << " against " << regx << " ... ";
if(reg(s.begin(), s.end(), regx.begin(), regx.end())){
cout << "MATCH !" << endl;
return true;
}else{
cout << "no match found." <<endl;
return false;
}
}
int main(){
string text = "baaabab";
isMatch(text, "ba*a++");
isMatch(text, "ba*a+");
isMatch(text, "a*ab");
isMatch("","+");
}
#include <iostream>
#include <string>
using namespace std;
typedef string::iterator iter;
bool reg(iter is, iter ie, iter rs, iter re){
//cout << *is << " " << *rs << endl;
if(is == ie && rs == re)
return true;
if(is == ie && rs != re){
if(*rs == '+') return reg(is,ie,++rs,re);
if(*rs == '*') return reg(is,ie,++rs,re);
return false;
}
if(is != ie && rs == re)
return false;
if(*rs == '+')
return reg(++is,ie,++rs,re);
if(*rs == '*'){
bool r;
rs++;
while(is != ie){
r |= reg(++is,ie,rs,re);
}
return r;
}
if(*is == *rs)
return reg(++is,ie,++rs,re);
if(*is != *rs)
return false;
}
//wrapper
bool isMatch(string s, string regx){
cout << "Checking " << s << " against " << regx << " ... ";
if(reg(s.begin(), s.end(), regx.begin(), regx.end())){
cout << "MATCH !" << endl;
return true;
}else{
cout << "no match found." <<endl;
return false;
}
}
int main(){
string text = "baaabab";
isMatch(text, "ba*a++");
isMatch(text, "ba*a+");
isMatch(text, "a*ab");
isMatch("","+");
}
Output:
Checking baaabab against ba*a++ ... MATCH !
Checking baaabab against ba*a+ ... MATCH !
Checking baaabab against a*ab ... no match found.
Checking against + ... MATCH !
...Program finished with exit code 0
Press ENTER to exit console.
P.S. Sorry for the spam above, couldn't tell if the post worked or not...dang it.
//C#
public static class Regex
{
public static bool IsMatch(string text, string regex)
{
if (regex.Length == 0)
return text.Length == 0;
if (regex[0] == '+')
return (IsMatch(text, regex.Substring(1)) || text.Length > 0 && IsMatch(text.Substring(1), regex.Substring(1)));
if (regex[0] == '*')
if (text.Length > 0)
for (int i = text.Length - 1; i > -1; i--)
{
if (IsMatch(text.Substring(i), regex.Substring(1)))
return true;
}
else return true;
if (text.Length > 0 && text[0] == regex[0])
return IsMatch(text.Substring(1), regex.Substring(1));
return false;
}
}
took @Gabriels code, made it purely recursive and added missing case.
If you start thinking recursive it's easy:
- for the +: must advance the pattern, but two options with the string, advance or not
- for the *: three options: advance pattern and string, advance only pattern, advance only string
- if not + and not *: if they match advance pattern and string
- termination: if pattern reached the end but string didn't (no match), if both reached the end (match)
do not forget all the border cases, so there is no buffer overrun
#include <iostream>
#include <string>
using namespace std;
using iter = string::iterator;
bool reg(iter is, iter ie, iter rs, iter re)
{
if (is == ie && rs == re) return true;
if (rs == re) return false;
if (*rs == '+') {
if (reg(is, ie, rs + 1, re)) return true; // advance pattern but not input (empty character)
return (is != ie) && reg(is + 1, ie, rs + 1, re); // advance input and pattern, if input not at the end
}
if (*rs == '*') {
if (reg(is, ie, rs + 1, re)) return true; // advance pattern but not input (empty sequence)
return (is != ie) && (reg(is + 1, ie, rs, re) || reg(is + 1, ie, rs + 1, re)); // advance input but not patter OR advance input and pattern
}
return (is != ie) && (*is == *rs) && reg(is + 1, ie, rs + 1, re); // if they match recurse
}
void test(string s, string regx, bool match) {
cout << "TEST CASE input: '" << s << "' expression '" << regx << "'"
<< (reg(s.begin(), s.end(), regx.begin(), regx.end()) == match ? " PASSED" : " FAILED")
<< endl;
}
int main() {
test("baaabab", "ba*a++", true);
test("baaabab", "ba*a+", true);
test("baaabab", "a*ab", false);
test("", "", true);
test("1", "", false);
test("", "+", true);
test(" ", "+", true);
test(" ", "+*", true);
test(" ", "+++", true);
test(" ", "+**", true);
test("", "+**", true);
test("", "+**+", true);
test("a", "+**+", true);
test("zzaazzuu", "+**+", true);
test("zzaazzuup", "+*p*+", true);
test("zzaazzuup", "+a**+", false);
test("aaaaaa", "+**", true);
test("aaaabbba", "+**", false);
test("aabc", "a+++bc", true);
return 0;
}
so what's space and runtime complexity (n is length string, m is length pattern)
space is the stack, and the stack depth will never exceed O(m + n) (actually O(max(n,m)) because it will always follow a branch to the end where it fails latest or succeeds.
worst case time is trickier:
- theoretically it branches of at the * case three times O(3 ^ (n + m))
- practically string: zzzq, pattern: ***z
how to improve is an interesting discussion here:
- preprocessing the pattern to only test the suffix if prefixes are common: this is not trivial with the * and +
- creating an automaton, in it's core the same as above
- no of them is trivial, there is a simpler dp way hidden in the recursion so one can prune some branches for example, if the pattern position and string position has already been senn, one can store the result already obtained. That way it should come down to O(m*n) when adding memoization.
private bool IsMatch(string str, string regex, int strIndex, int regexIndex)
{
if (strIndex == str.Length && regexIndex == regex.Length) //we reached the end of the string and the regex
return true;
var i = strIndex;
var j = regexIndex;
// Advance while the two characters are identical
while (i < str.Length && j < regex.Length && str[i] == regex[j])
{
i++;
j++;
}
if (i == str.Length && j == regex.Length) return true; // we reached the end of the string and regex
if (i == str.Length) //we are at the end of the string, if the regex are all */+ then we are good
{
for (; j < regex.Length; j++)
if (regex[j] != '+' && regex[j] != '*') return false;
return true; // the remaining of the regex is all * and/or +
}
// Case 1: we recahed the end of the regex but not of the string
// Case 2: this means both are not empty and the first non-matching is neither * nor +
if (j == regex.Length || regex[j] != '+' && regex[j] != '*') return false;
if (regex[j] == '+')
return IsMatch(str, regex, i + 1, j + 1) || IsMatch(str, regex, i, j + 1);
// it has to be '*'
return IsMatch(str, regex, i, j + 1) || IsMatch(str, regex, i + 1, j) || IsMatch(str, regex, i + 1, j + 1);
}
def match(s, p):
n = len(s)
m = len(p)
ms = [[False] * (m + 1) for _ in xrange(n + 1)]
ms[0][0] = True
for j in xrange(1, m+1):
ms[0][j] = ms[0][j-1] and p[j-1] in ['*', '+']
for i in xrange(1, n+1):
for j in xrange(1, m+1):
if p[j-1] == '*':
ms[i][j] = ms[i][j-1] or ms[i-1][j]
elif p[j-1] == '+':
ms[i][j] = ms[i][j-1] or ms[i-1][j-1]
else:
ms[i][j] = p[j-1] == s[i-1] and ms[i-1][j-1]
return ms[n][m]
//Rextester.Program.Main is the entry point for your code. Don't change it.
//Compiler version 4.0.30319.17929 for Microsoft (R) .NET Framework 4.5
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;
namespace Rextester
{
public class Program
{
public static void Main(string[] args)
{
//Your code goes here
Console.WriteLine("Hello, world!");
Pattern pattern = new Pattern("baaababc", 0, "ba*a+c", 0);
bool result = pattern.getResult();
Console.WriteLine(result.ToString());
}
}
public class Pattern {
private string text;
private int posText;
private string patt;
private int posPatt;
public Pattern(string text, int posText, string patt, int posPatt) {
this.text = text;
this.posText = posText;
this.patt = patt;
this.posPatt = posPatt;
}
public bool getResult() {
while(posPatt != patt.Length) {
if (posText >= text.Length) return false;
if (patt[posPatt] == text[posText]) {
posPatt++;
posText++;
continue;
}
if (patt[posPatt] == '*') {
posPatt++;
for (int i = posText+1; i < text.Length; i++) {
Pattern pattern = new Pattern(text, i, patt, posPatt);
if (pattern.getResult()) return true;
}
continue;
}
if (patt[posPatt] == '+') {
posPatt++;
Pattern pattern = new Pattern(text, posText+1, patt, posPatt);
if (pattern.getResult()) return true;
continue;
}
return false;
}
if (posText == text.Length) return true;
return false;
}
}
}
//Rextester.Program.Main is the entry point for your code. Don't change it.
//Compiler version 4.0.30319.17929 for Microsoft (R) .NET Framework 4.5
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;
namespace Rextester
{
public class Program
{
public static void Main(string[] args)
{
//Your code goes here
Console.WriteLine("Hello, world!");
Pattern pattern = new Pattern("baaababc", 0, "ba*a+c", 0);
bool result = pattern.getResult();
Console.WriteLine(result.ToString());
}
}
public class Pattern {
private string text;
private int posText;
private string patt;
private int posPatt;
public Pattern(string text, int posText, string patt, int posPatt) {
this.text = text;
this.posText = posText;
this.patt = patt;
this.posPatt = posPatt;
}
public bool getResult() {
while(posPatt != patt.Length) {
if (posText >= text.Length) return false;
if (patt[posPatt] == text[posText]) {
posPatt++;
posText++;
continue;
}
if (patt[posPatt] == '*') {
posPatt++;
for (int i = posText+1; i < text.Length; i++) {
Pattern pattern = new Pattern(text, i, patt, posPatt);
if (pattern.getResult()) return true;
}
continue;
}
if (patt[posPatt] == '+') {
posPatt++;
Pattern pattern = new Pattern(text, posText+1, patt, posPatt);
if (pattern.getResult()) return true;
continue;
}
return false;
}
if (posText == text.Length) return true;
return false;
}
}
}
//Rextester.Program.Main is the entry point for your code. Don't change it.
//Compiler version 4.0.30319.17929 for Microsoft (R) .NET Framework 4.5
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;
namespace Rextester
{
public class Program
{
public static void Main(string[] args)
{
//Your code goes here
Console.WriteLine("Hello, world!");
Pattern pattern = new Pattern("baaababc", 0, "ba*a+c", 0);
bool result = pattern.getResult();
Console.WriteLine(result.ToString());
}
}
public class Pattern {
private string text;
private int posText;
private string patt;
private int posPatt;
public Pattern(string text, int posText, string patt, int posPatt) {
this.text = text;
this.posText = posText;
this.patt = patt;
this.posPatt = posPatt;
}
public bool getResult() {
while(posPatt != patt.Length) {
if (posText >= text.Length) return false;
if (patt[posPatt] == text[posText]) {
posPatt++;
posText++;
continue;
}
if (patt[posPatt] == '*') {
posPatt++;
for (int i = posText+1; i < text.Length; i++) {
Pattern pattern = new Pattern(text, i, patt, posPatt);
if (pattern.getResult()) return true;
}
continue;
}
if (patt[posPatt] == '+') {
posPatt++;
Pattern pattern = new Pattern(text, posText+1, patt, posPatt);
if (pattern.getResult()) return true;
continue;
}
return false;
}
if (posText == text.Length) return true;
return false;
}
}
}
//Rextester.Program.Main is the entry point for your code. Don't change it.
//Compiler version 4.0.30319.17929 for Microsoft (R) .NET Framework 4.5
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;
namespace Rextester
{
public class Program
{
public static void Main(string[] args)
{
//Your code goes here
Console.WriteLine("Hello, world!");
Pattern pattern = new Pattern("baaababc", 0, "ba*a+c", 0);
bool result = pattern.getResult();
Console.WriteLine(result.ToString());
}
}
public class Pattern {
private string text;
private int posText;
private string patt;
private int posPatt;
public Pattern(string text, int posText, string patt, int posPatt) {
this.text = text;
this.posText = posText;
this.patt = patt;
this.posPatt = posPatt;
}
public bool getResult() {
while(posPatt != patt.Length) {
if (posText >= text.Length) return false;
if (patt[posPatt] == text[posText]) {
posPatt++;
posText++;
continue;
}
if (patt[posPatt] == '*') {
posPatt++;
for (int i = posText+1; i < text.Length; i++) {
Pattern pattern = new Pattern(text, i, patt, posPatt);
if (pattern.getResult()) return true;
}
continue;
}
if (patt[posPatt] == '+') {
posPatt++;
Pattern pattern = new Pattern(text, posText+1, patt, posPatt);
if (pattern.getResult()) return true;
continue;
}
return false;
}
if (posText == text.Length) return true;
return false;
}
}
}
//Rextester.Program.Main is the entry point for your code. Don't change it.
//Compiler version 4.0.30319.17929 for Microsoft (R) .NET Framework 4.5
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;
namespace Rextester
{
public class Program
{
public static void Main(string[] args)
{
//Your code goes here
Console.WriteLine("Hello, world!");
Pattern pattern = new Pattern("baaababc", 0, "ba*a+c", 0);
bool result = pattern.getResult();
Console.WriteLine(result.ToString());
}
}
public class Pattern {
private string text;
private int posText;
private string patt;
private int posPatt;
public Pattern(string text, int posText, string patt, int posPatt) {
this.text = text;
this.posText = posText;
this.patt = patt;
this.posPatt = posPatt;
}
public bool getResult() {
while(posPatt != patt.Length) {
if (posText >= text.Length) return false;
if (patt[posPatt] == text[posText]) {
posPatt++;
posText++;
continue;
}
if (patt[posPatt] == '*') {
posPatt++;
for (int i = posText+1; i < text.Length; i++) {
Pattern pattern = new Pattern(text, i, patt, posPatt);
if (pattern.getResult()) return true;
}
continue;
}
if (patt[posPatt] == '+') {
posPatt++;
Pattern pattern = new Pattern(text, posText+1, patt, posPatt);
if (pattern.getResult()) return true;
continue;
}
return false;
}
if (posText == text.Length) return true;
return false;
}
}
}
O(nm) time and space.
#include <string>
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
bool Match(const string& s, const string& p, unordered_map<uint64_t, bool>& memo, int idx_s = 0, int idx_p = 0)
{
if (idx_s < 0 ||
idx_s > s.size() ||
idx_p < 0 ||
idx_p > p.size())
{
return false;
}
if (idx_s == s.size() &&
idx_p == p.size())
{
return true;
}
if (idx_s == s.size())
{
if (p[idx_p] == '*' ||
p[idx_p] == '+')
{
return Match(s, p, memo, idx_s, idx_p + 1);
}
else
{
return false;
}
}
if (idx_p == p.size())
{
return !p.empty() && p.back() == '*';
}
uint64_t memo_key = (static_cast<uint64_t>(idx_s) << 32) | idx_p;
auto it = memo.find(memo_key);
if (it != memo.end())
{
return it->second;
}
bool res = false;
if (p[idx_p] == '*')
{
for (int i = idx_s + 1; i <= s.size() && !res; ++i)
{
res |= Match(s, p, memo, i, idx_p);
}
if(!res)
{
res = Match(s, p, memo, idx_s, idx_p + 1);
}
}
else if (p[idx_p] == '+')
{
res = Match(s, p, memo, idx_s + 1, idx_p + 1) |
Match(s, p, memo, idx_s, idx_p + 1);
}
else
{
res = s[idx_s] == p[idx_p]
? Match(s, p, memo, idx_s + 1, idx_p + 1)
: false;
}
memo[memo_key] = res;
return res;
}
int main()
{
vector<pair<string, string>> test_cases =
{
{"baaabab", "ba*a++"},
{"baaabab", "ba*a+"},
{"baaabab", "a*ab"},
{"", "+"},
{"baaabab", "ba+"},
{"baaabab", "ba*"},
{"ba", "*+**++a+*+**++"}
};
unordered_map<uint64_t, bool> memo;
for (auto t : test_cases)
{
memo.clear();
cout << Match(t.first, t.second, memo) << "\n";
}
return 0;
}
- guilhebl May 17, 2018public static boolean isMatch(String str, String pattern) { int n = str.length(); int m = pattern.length(); if (m == 0 && n == 0) return true; boolean[][] t = new boolean[n + 1][m + 1]; for(int i = 0; i < n + 1; i++) Arrays.fill(t[i], false); t[0][0] = true; for (int j = 1; j <= m; j++) { if (pattern.charAt(j - 1) == '*' || (pattern.charAt(j - 1) == '+')) { t[0][j] = t[0][j - 1]; } } for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { if (pattern.charAt(j - 1) == '*') { t[i][j] = t[i][j - 1] || t[i - 1][j]; } else if (pattern.charAt(j - 1) == '+') { t[i][j] = t[i][j - 1] || t[i - 1][j - 1]; } else if (str.charAt(i - 1) == pattern.charAt(j - 1)) { t[i][j] = t[i - 1][j - 1]; } else { t[i][j] = false; } } } return t[n][m]; }