Google Interview Question


Country: United States
Interview Type: Phone Interview




Comment hidden because of low score. Click to expand.
2
of 2 vote

One approach, if we're assuming multiple accesses to the data (otherwise linear find is best) is to set up a Trie where the node is the start of each subsequent word. In the trie we store indexes that match the current pattern.

That way, for any given pattern we can quickly get the indexes that can match the pattern based on the start of the camelcased words and we perform an individual match on those.

private List<String> matchesCCPattern(String[] words, String pattern) {
    CCTrieNode root = new CCTrieNode();
    for (int i = 0; i < words.length; i++) {
      root.insert(words[i], i);
    }

    List<String> matchingWords = new ArrayList<>();
    for (int index : root.indexesForCCPattern(pattern)) {
      if (matchesPattern(words[index], pattern)) {
        matchingWords.add(words[index]);
      }
    }
    return matchingWords;
  }

  private boolean matchesPattern(String word, String pattern) {
    int wordIndex = 0, patternIndex = 0;
    while (wordIndex < word.length() && patternIndex < pattern.length()) {
      char wordChar = word.charAt(wordIndex), patternChar = pattern.charAt(patternIndex);
      if (Character.isUpperCase(wordChar) || !Character.isUpperCase(patternChar)) {
        if (wordChar != patternChar) return false;
        patternIndex++;
      }
      wordIndex++;
    }
    return patternIndex == pattern.length();
  }

  private class CCTrieNode {
    private CCTrieNode[] next = new CCTrieNode[26];
    private List<Integer> matchesIndex = new ArrayList<>();

    private void insert(String words, int index) {
      matchesIndex.add(index);
      if (words.isEmpty()) return;

      CCTrieNode nextWord = next[words.charAt(0) - 'A'];
      if (nextWord == null) {
        nextWord = new CCTrieNode();
        next[words.charAt(0) - 'A'] = nextWord;
      }
      int nextWordStart = 0;
      while (++nextWordStart < words.length()) {
        if (Character.isUpperCase(words.charAt(nextWordStart))) break;
      }
      nextWord.insert(words.substring(nextWordStart), index);
    }

    private List<Integer> indexesForCCPattern(String pattern) {
      if (pattern.isEmpty()) return matchesIndex;
      CCTrieNode nextWordNode = next[pattern.charAt(0) - 'A'];
      if (nextWordNode == null) {
        return Collections.emptyList();
      }
      int nextWordStart = 0;
      while (++nextWordStart < pattern.length()) {
        if (Character.isUpperCase(pattern.charAt(nextWordStart))) break;
      }
      return nextWordNode.indexesForCCPattern(pattern.substring(nextWordStart));
    }
  }

- Johnie July 08, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

package com.gregrode.questions;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.List;
import java.util.Queue;
import java.util.stream.Collectors;

public class CamelCaseNotation
{

	private String[] camelCaseWords = { "HelloMars", "HelloWorld", "HelloWorldMars", "HiHo" };

	public List<String> testCamelCase(final String pattern)
	{
		return Arrays.stream(camelCaseWords).filter(word -> isMatchingCamelCase(pattern, word)).collect(Collectors.toList());
	}

	private Queue<String> toQueue(final String word)
	{
		final Queue<String> queue = new ArrayDeque<>(word.length());
		for (final char ch : word.toCharArray())
		{
			queue.add(String.valueOf(ch));
		}
		return queue;
	}

	private boolean isMatchingCamelCase(final String pattern, final String word)
	{
		if (pattern.length() > word.length())
		{
			return false;
		}

		final Queue<String> patternQueue = toQueue(pattern);
		final Queue<String> wordQueue = toQueue(word);
		String ch = patternQueue.remove();
		while (!wordQueue.isEmpty())
		{
			if (ch.equals(wordQueue.remove()))
			{
				if (patternQueue.isEmpty())
				{
					return true;
				}
				ch = patternQueue.remove();
				continue;
			}

			if (!Character.isUpperCase(ch.charAt(0)))
			{
				return false;
			}
		}
		return false;
	}
}

- Greg July 08, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

If at all I understood the question correctly, then here is my answer is in Python language

def camelcase(string, substring):
    flag = False
    arr = []
    if substring[-1].islower() or substring[0].islower():
        return []
    #return [i for i in string for j in substring if j in i]
    for i in string:
        for j in substring:
            if j not in i:
                flag = True
                break
        if flag == False:
            arr.append(i)
        flag = False
    return arr

print camelcase(['HelloMars', 'HelloWorld', 'HelloWorldMars', 'HiHo'], 'HeWorM')

- rasmiranjanbabu July 08, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

import java.util.*;
public class camelcaseGoogle {
public static void main(String args[]){
	ArrayList<String> list = new ArrayList<String>();
	list.add("HiHello");
	list.add("HelloYou");
	list.add("HelloYouThere");
	ArrayList<String> patternList = new ArrayList<String>();
	Scanner sc = new Scanner(System.in);
	String pattern = sc.next();int flag =0;
	for(int i=0;i<list.size();i++){
		String s = list.get(i);
		int len =0; int pattern_len = pattern.length()-1; int pat =0;
		
		while((len!=s.length()-1 && pat !=pattern.length()-1) || flag !=1){
		if(s.charAt(len)== pattern.charAt(pat)){
				len ++; 
				if(pat<pattern_len){pat ++;}
				else break;
			}
			else if(len!=0 && pat !=0 && len!=s.length()-1) len ++;
			else flag =1;
		}
		if (flag == 0)
		{
			patternList.add(s);
		}
		else flag = 0;
	}
	
	System.out.println(patternList);
	
}
}

- shruthi July 08, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.*;
public class camelcaseGoogle {
public static void main(String args[]){
	ArrayList<String> list = new ArrayList<String>();
	list.add("HiHello");
	list.add("HelloYou");
	list.add("HelloYouThere");
	ArrayList<String> patternList = new ArrayList<String>();
	Scanner sc = new Scanner(System.in);
	String pattern = sc.next();int flag =0;
	for(int i=0;i<list.size();i++){
		String s = list.get(i);
		int len =0; int pattern_len = pattern.length()-1; int pat =0;
		
		while((len!=s.length()-1 && pat !=pattern.length()-1) || flag !=1){
		if(s.charAt(len)== pattern.charAt(pat)){
				len ++; 
				if(pat<pattern_len){pat ++;}
				else break;
			}
			else if(len!=0 && pat !=0 && len!=s.length()-1) len ++;
			else flag =1;
		}
		if (flag == 0)
		{
			patternList.add(s);
		}
		else flag = 0;
	}
	
	System.out.println(patternList);
	
}
}

- Shruthi Prakash July 08, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.*;
public class camelcaseGoogle {
public static void main(String args[]){
	ArrayList<String> list = new ArrayList<String>();
	list.add("HiHello");
	list.add("HelloYou");
	list.add("HelloYouThere");
	ArrayList<String> patternList = new ArrayList<String>();
	Scanner sc = new Scanner(System.in);
	String pattern = sc.next();int flag =0;
	for(int i=0;i<list.size();i++){
		String s = list.get(i);
		int len =0; int pattern_len = pattern.length()-1; int pat =0;
		
		while((len!=s.length()-1 && pat !=pattern.length()-1) || flag !=1){
		if(s.charAt(len)== pattern.charAt(pat)){
				len ++; 
				if(pat<pattern_len){pat ++;}
				else break;
			}
			else if(len!=0 && pat !=0 && len!=s.length()-1) len ++;
			else flag =1;
		}
		if (flag == 0)
		{
			patternList.add(s);
		}
		else flag = 0;
	}
	
	System.out.println(patternList);
	
}
}

- Shruthi Prakash July 08, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Assuming a pattern is either valid camel case or an empty string.
Assuming the list is always an array.

Javascript:

function getMatchingElements(list, pattern) {
  return list.filter(doesMatch(pattern));
}

function doesMatch(pattern) {
  return function(element) {
    var p = new String(pattern);
    while(p.length > 0) {
      var nextCapitalIndex = findNextCapitalIndex(p);
      var subPattern = p.substr(0, nextCapitalIndex);
      if(element.substr(0, subPattern.length) !== subPattern) {
        return false;
      }
      p = p.substr(subPattern.length);
      element = element.substr(findNextCapitalIndex(element));
    }
    return true;
  }
}

function findNextCapitalIndex(str) {
  for(var i = 1; i < str.length; i++) {
   var c = str.charAt(i);
   if(c === c.toUpperCase()) {
     return i;
   }
  }
  return Number.POSITIVE_INFINITY;
}

- Anonymous July 08, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here are the steps:
1) Loop for each word in the list, create a boolean[] wordsFlags = new boolean[256]
2) set true on those ASCI characters which are present in the word..
3) Get the pattern word and check each char of the pattern word is present in wordsFlag
4) if all characters are present then add that word to the list of matching words..
5) return all the matching words

- sudheer July 08, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package com.gregrode.questions;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.List;
import java.util.Queue;
import java.util.stream.Collectors;

public class CamelCaseNotation
{

private String[] camelCaseWords = { "HelloMars", "HelloWorld", "HelloWorldMars", "HiHo" };

public List<String> testCamelCase(final String pattern)
{
return Arrays.stream(camelCaseWords).filter(word -> isMatchingCamelCase(pattern, word)).collect(Collectors.toList());
}

private Queue<String> toQueue(final String word)
{
final Queue<String> queue = new ArrayDeque<>(word.length());
for (final char ch : word.toCharArray())
{
queue.add(String.valueOf(ch));
}
return queue;
}

private boolean isMatchingCamelCase(final String pattern, final String word)
{
if (pattern.length() > word.length())
{
return false;
}

final Queue<String> patternQueue = toQueue(pattern);
final Queue<String> wordQueue = toQueue(word);
String ch = patternQueue.remove();
while (!wordQueue.isEmpty())
{
if (ch.equals(wordQueue.remove()))
{
if (patternQueue.isEmpty())
{
return true;
}
ch = patternQueue.remove();
continue;
}

if (!Character.isUpperCase(ch.charAt(0)))
{
return false;
}
}
return false;
}
}

- gregrode July 08, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I used a trie with random pointers and a boolean attribute in each trie node to indicate if it's the start of a word in the initial list.

//Time Complexity: Tree building-O(NL) where N is the number of words to be added and L is the length of the longest word. Pattern Querying-O(P) where P is the length of the pattern.


public class Node{
		
		
		 Node[] arr;
		ArrayList<String> ls;
		boolean isWordStart;
		
		public Node{
			arr=new Node[128];
			ls=new ArrayList<String>();
			isWordStart=false;
		
			for(int i=0;i<pointers.length;i++)
			{
				pointers[i]=new ArrayList<Node>();
			}
			
		}
	
}


public class Solution
{
	Node rt;
	
	
	public Solution(String[] arr)
	{
		rt=new Node();
	
		buildTree(arr);
		
	}
	
	private void buildTree(String[] arr)
	{
		for(String s:arr)
		{
			addToTree(rt,s);
			rt.arr[(int)s.charAt(0)].isWordStart=true;
		}
	}
	
	public ArrayList<String>query(String patt)
	{
		if(patt==null||patt.length()==0||rt==null)
		{
			return null;
		}
		return(findMatches(String p));
		
	}
	
	private ArrayList<String> findMatches(String p)
	{
		Node v=rt.arr[(int)p.charAt(0)]==null||!rt.arr[(int)p.charAt(0)].isWordStart?null:rt.arr[(int)p.charAt(0)];
		ArrayList<String> ls=new ArrayList<String>();
		
		for(int i=1;i<p.length();i++)
		{
			int idx=(int)p.charAt(i);
			if(v[idx]==null)
			{
				
				v=null;
				break;
			}
			v=v[idx];
				
		}
		
		if(v!=null)
		{
			ls.addAll(v.ls);
		}
		return ls;
		
	}
	
	
	
	
	private void addToTree(Node r,String str)
	{
		
		int lastIdx=str.length();
		for(int i=str.length()-1; i>=0;i--)
		{
			int idx=(int)str.charAt(i);
			if(isUpperCase(str.charAt(i)))
			{
			  addHelper(r,str.substring(i,lastIdx),lastIdx);	
			  lastIdx=i;
			}
		}
	}
	
	private boolean isUpperCase(char c)
	{
		return (int)(c-'A')==0;
	}
	
	private void addHelper(Node rt,String s,lastIdx)
	{
		if(rt.arr[(int)s.charAt(0)]==null)
		{
			rt.arr[(int)s.charAt(0)]=new Node();
		}
		Node v=rt.arr[(int)s.charAt(0)];
		for(int i=1;i<s.length();i++)
		{
			int idx=(int)s.charAt(i);
			if(v.arr[idx]==null)
			{
				v.arr[idx]=new Node();
				
			
			}
			if(lastIdx<s.length())
			{
			v.arr[(int)s.charAt(lastIdx)]=rt.arr[(int)s.charAt(lastIdx)];
			}
			v=v.arr[idx];
			v.add(s);
			
			
		}
		if(lastIdx<s.length())
			{
			v.arr[(int)s.charAt(lastIdx)]=rt.arr[(int)s.charAt(lastIdx)];
			}
		
		
	}
}

- divm01986 July 08, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote
Can somebody make me understand if {{{HeWorM -> [HelloWorldMars] #contains caps and small letter}}} then why, {{{Ho -> [] # is not returning [HiHo]?????}}} What would happen if we are looking for {{{{{{HeWorMa -> [HelloWorldMars] # or [] empty list? }}} Anyways, if at all I have understood the question correctly, then here is my answer in Python {{{ def camelcase(string, substring): flag = False arr = [] if substring[-1].islower() or substring[0].islower(): return [] #return [i for i in string for j in substring if j in i] for i in string: for j in substring: if j not in i: flag = True break if flag == False: arr.append(i) flag = False return arr print camelcase(['HelloMars', 'HelloWorld', 'HelloWorldMars', 'HiHo'], 'HeWorM') }}} - rasmiranjanbabu July 08, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

My understanding is that the search string has to start with the first capital letter.

def check_a_string(s, d):

    def nextup(d, di):
        while d[di].islower():
            di += 1
            if di >= len(d):
                return -1
        return di

    di = 0

    #first char has to match
    if s[0] != d[0]:
        return False

    for c in s[1:]:
        if c.isupper():
            di = nextup(d, di)
        else:
            di += 1

        if (di == -1) or (c != d[di]):
            return False

    return True




def check(input, l):
    for s in l:
        if check_a_string(input, s):
            yield s


l = ['HelloMars', 'HelloWorld', 'HelloWorldMars', 'HiHo']
search_strings = ["H", "HW", "Ho", "HeWorM"]

for t in search_strings:
    result = list(check(t, l))
    
    print(t)
    print(result)

- chromehearts July 09, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Why can't the following be the solution?

static void Main(string[] args)
        {
            string[] words = new string[] {"HelloMars", "HelloWorld", "HelloWorldMars", "HiHo"};
            string[] patterns = new string[] {"H", "HW", "Ho", "HeWorM" };

            foreach (string pattern in patterns)
            {
                Console.Write(pattern + " -> [");
                string comma = string.Empty;
                foreach (string match in GetFilteredItems(words, pattern))
                {
                    Console.Write(comma + match);
                    comma = ", ";
                }
                Console.WriteLine("]");
            }
            Console.ReadKey();
        }

        static IEnumerable<string> GetFilteredItems(IEnumerable<string> words, string pattern)
        {
            return from word in words
                where IsMatch(word, pattern, 0, 0)
                select word;
        }

        static bool IsMatch(string word, string pattern, int wordIndex, int patternIndex)
        {
            if (string.IsNullOrEmpty(pattern) || patternIndex >= pattern.Length)
                return true;
            if (string.IsNullOrEmpty(word) || wordIndex >= word.Length)
                return false;

            if (pattern[patternIndex] == word[wordIndex])
                return IsMatch(word, pattern, wordIndex + 1, patternIndex + 1);
            if (char.IsUpper(word[wordIndex]) || char.IsLower(pattern[patternIndex]))
                return false;
            return IsMatch(word, pattern, wordIndex + 1, patternIndex);
        }

- Daniel Cohen July 10, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class prac2 {
	public static void main(String[] args) {
		List<String> strList = new ArrayList<String>();
		strList.add("HelloWorld");
		strList.add("HelloWorldMars");
		strList.add("HelloMars");
		String pattern = "HW";
		List <String> returnList = findClasses(strList,pattern);
		System.out.print(returnList);
	}
		public static List<String> findClasses(List<String> strList, String pattern){
		List<String> resultList = new ArrayList<String> ();
		for(String str : strList){
			String  substring[] = str.split("[^A-Z]+");
			StringBuilder camelCaseStr = new StringBuilder();
			for(String s : substring){
				camelCaseStr.append(s);
			}
			if(camelCaseStr.toString().contains(pattern)){
				resultList.add(str);
			}
		}
		return resultList;
	}
}

- Shivani R July 13, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

In RUBY

def camel_case_notation(str_arr, patt)
	if patt.nil? || patt.length == 0 || str_arr.nil? || 
		str_arr.length == 0 || is_lower?(patt[0])
	  	return []
	end

	patt_arr = break_pattern(patt)
	result = []
	str_arr.each do |str|
		if fits_pattern(patt_arr, str)
			result << str
		end
	end

	result
end

def is_upper?(char)
	char == char.upcase
end

def is_lower? char
	char == char.downcase
end

def break_pattern(pattern)
	temp = pattern[0]
	pattern_arr = []
	1.upto(pattern.length-1).each do |i|
		if is_upper? pattern[i]
			pattern_arr << temp
			temp = pattern[i]
		elsif is_lower? pattern[i]
			temp << pattern[i]
		else
			raise 'Unknown character'
		end
	end
	pattern_arr << temp
	pattern_arr
end	

def fits_pattern(pattern_arr, str)
	p = 0
	s = 0
	while p < pattern_arr.length
		pattern = pattern_arr[p]
		if str.length >= s + pattern.length && pattern == str[s..s+pattern.length-1]
			p += 1
			s += pattern.length
			while (s < str.length && is_lower?(str[s]))
				s += 1
			end
		else
			return false
		end
	end
	true
end

- goonie July 13, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def camel_case_notation(str_arr, patt)
	if patt.nil? || patt.length == 0 || str_arr.nil? || 
		str_arr.length == 0 || is_lower?(patt[0])
	  	return []
	end

	patt_arr = break_pattern(patt)
	result = []
	str_arr.each do |str|
		if fits_pattern(patt_arr, str)
			result << str
		end
	end

	result
end

def is_upper?(char)
	char == char.upcase
end

def is_lower? char
	char == char.downcase
end

def break_pattern(pattern)
	temp = pattern[0]
	pattern_arr = []
	1.upto(pattern.length-1).each do |i|
		if is_upper? pattern[i]
			pattern_arr << temp
			temp = pattern[i]
		elsif is_lower? pattern[i]
			temp << pattern[i]
		else
			raise 'Unknown character'
		end
	end
	pattern_arr << temp
	pattern_arr
end	

def fits_pattern(pattern_arr, str)
	p = 0
	s = 0
	while p < pattern_arr.length
		pattern = pattern_arr[p]
		if str.length >= s + pattern.length && pattern == str[s..s+pattern.length-1]
			p += 1
			s += pattern.length
			while (s < str.length && is_lower?(str[s]))
				s += 1
			end
		else
			return false
		end
	end
	true
end

- jimun July 13, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>
#include <string>
#include <vector> 
using namespace std;

bool checkLowerCase(char& ch){    // ==========> each element of string has type char& (reference)
    return (ch >= 'a' && ch <= 'z');
}

bool check(string givenString, string pattern){
    int i = 0, j = 0;
    while (i < (int)givenString.size() && j < (int)pattern.size()){
        if (checkLowerCase(givenString[i]) || checkLowerCase(pattern[j]) || givenString[i] != pattern[j]) return false;
        i++; j++;

        while (i < (int)givenString.size() && j < (int)pattern.size() && checkLowerCase(givenString[i]) && checkLowerCase(pattern[j]) && givenString[i] == pattern[j]){
            i++;j++;
        }; 
        if (j == (int)pattern.size()) {
            //Last part to check in pattern

            return true;
        } else if (!checkLowerCase(pattern[j])) {
            //Current part is satisfied, go to the next position in givenString
            while (checkLowerCase(givenString[i]) && checkLowerCase(givenString[i])) i++;
        } else {
            return false;
        }
    }
    return false;
}

vector<string> findMatchingStrings(vector<string> stringList, string pattern){
    vector<string> res;
   
    for (int i = 0; i < (int)stringList.size(); i++){
         
        if (check(stringList[i], pattern)){
            res.push_back(stringList[i]);
        } 
    }
    return res;
}

void printVector(vector<string> myVector){
    cout << "Size of vector: "  << myVector.size() << endl;

    for (int i = 0; i < (int)myVector.size(); i++){
        cout << myVector[i] << " ";
    }
    cout << endl;
}

int main()
{
   cout << "Hello World" << endl; 
   //['HelloMars', 'HelloWorld', 'HelloWorldMars', 'HiHo'] 

   string st1("HelloMars");
   string st2("HelloWorld");
   string st3("HelloWorldMars");
   string st4("Hiho");                                // ==========> init string (giong het ben duoi)         

   vector<string> stringList {st1, st2, st3, st4};    // ==========> init vector by vector<int> a {1,2,3}

   string pt1("H");
   string pt2("HW");
   string pt3("Ho");
   string pt4("HeWorM");
   printVector(stringList);
   printVector(findMatchingStrings(stringList, pt1));
   printVector(findMatchingStrings(stringList, pt2));
   printVector(findMatchingStrings(stringList, pt3));
   printVector(findMatchingStrings(stringList, pt4));

   return 0;
}

- Cuong Nguyen July 13, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>
#include <string>
#include <vector> 
using namespace std;

bool checkLowerCase(char& ch){    // ==========> each element of string has type char& (reference)
    return (ch >= 'a' && ch <= 'z');
}

bool check(string givenString, string pattern){
    int i = 0, j = 0;
    while (i < (int)givenString.size() && j < (int)pattern.size()){
        if (checkLowerCase(givenString[i]) || checkLowerCase(pattern[j]) || givenString[i] != pattern[j]) return false;
        i++; j++;

        while (i < (int)givenString.size() && j < (int)pattern.size() && checkLowerCase(givenString[i]) && checkLowerCase(pattern[j]) && givenString[i] == pattern[j]){
            i++;j++;
        }; 
        if (j == (int)pattern.size()) {
            //Last part to check in pattern

            return true;
        } else if (!checkLowerCase(pattern[j])) {
            //Current part is satisfied, go to the next position in givenString
            while (checkLowerCase(givenString[i]) && checkLowerCase(givenString[i])) i++;
        } else {
            return false;
        }
    }
    return false;
}

vector<string> findMatchingStrings(vector<string> stringList, string pattern){
    vector<string> res;
   
    for (int i = 0; i < (int)stringList.size(); i++){
         
        if (check(stringList[i], pattern)){
            res.push_back(stringList[i]);
        } 
    }
    return res;
}

void printVector(vector<string> myVector){
    cout << "Size of vector: "  << myVector.size() << endl;

    for (int i = 0; i < (int)myVector.size(); i++){
        cout << myVector[i] << " ";
    }
    cout << endl;
}

int main()
{
   cout << "Hello World" << endl; 
   //['HelloMars', 'HelloWorld', 'HelloWorldMars', 'HiHo'] 

   string st1("HelloMars");
   string st2("HelloWorld");
   string st3("HelloWorldMars");
   string st4("Hiho");                                // ==========> init string (giong het ben duoi)         

   vector<string> stringList {st1, st2, st3, st4};    // ==========> init vector by vector<int> a {1,2,3}

   string pt1("H");
   string pt2("HW");
   string pt3("Ho");
   string pt4("HeWorM");
   printVector(stringList);
   printVector(findMatchingStrings(stringList, pt1));
   printVector(findMatchingStrings(stringList, pt2));
   printVector(findMatchingStrings(stringList, pt3));
   printVector(findMatchingStrings(stringList, pt4));

   return 0;
}

- Cuong Nguyen July 13, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

bool check(string givenString, string pattern){
    int i = 0, j = 0;
    while (i < (int)givenString.size() && j < (int)pattern.size()){
        if (checkLowerCase(givenString[i]) || checkLowerCase(pattern[j]) || givenString[i] != pattern[j]) return false;
        i++; j++;

        while (i < (int)givenString.size() && j < (int)pattern.size() && checkLowerCase(givenString[i]) && checkLowerCase(pattern[j]) && givenString[i] == pattern[j]){
            i++;j++;
        }; 
        if (j == (int)pattern.size()) {
            //Last part to check in pattern

            return true;
        } else if (!checkLowerCase(pattern[j])) {
            //Current part is satisfied, go to the next position in givenString
            while (checkLowerCase(givenString[i]) && checkLowerCase(givenString[i])) i++;
        } else {
            return false;
        }
    }
    return false;

}

- Anonymous July 13, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

asdasd

- Anonymous July 13, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

An efficient solution in C++, does not need Regex nor extra space!

#include <iostream>
#include <vector>
#include <string>

void 
getCCPatterns(std::vector<std::string>& A, std::string& P) {
  for(int i = 0; i < A.size(); ++i) {
    std::string E = A[i];
    int c = 0;
    for(int j = 0; j < E.size() && c < P.size(); ++j) {
      if(islower(P[c]) && P[c] != E[j]) break;
      if(E[j] == P[c]) c++;
    }   
    if(c == P.length()) std::cout << E << std::endl;
  }
}

int main() {
  std::vector<std::string> A = {"HelloMars", "HelloWorld", "HelloWorldMars", "HiHo"};
  std::string P = "HeWorM";

  getCCPatterns(A, P); 
  return 0;
}

- fiska July 13, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static List<String> test(String pattern, List<String> inputList){
		List<String> result = new ArrayList<>();
		if(inputList != null && pattern != "null"){
			String[] splitedStrs = pattern.split("(?=\\p{Lu})"); 
			String reg = "^";
			for(String splitedStr : splitedStrs){
				System.out.println(splitedStr);
				reg += splitedStr+"[a-z]*";
			}
			System.out.println(reg);
			Pattern pat = Pattern.compile(reg);
			
			for(String input: inputList){
				Matcher matcher = pat.matcher(input);
				while(matcher.find()){
					result.add(input);
				}
			}
		}
		return result;
	}

- alvin July 15, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static ArrayList<String> matchedList(String[] list, String pattern){
        if(pattern.length() < 1 || pattern == null)
            return null;
        if(list.length < 1)
            return null;
        ArrayList<String> matchedPattern = new ArrayList<String>();
        int flag = 0;
        for( String str : list){
            if(pattern.length() > str.length())
                continue;
            if(pattern.charAt(0) != str.charAt(0))
                continue;
            else
                flag = 1;
            int position = 0;
            for(int i = 1; i < pattern.length(); i++){
                for( int j = position + 1; j < str.length(); j++) {
                    if (pattern.charAt(i) == str.charAt(j)) {
                        position = j;
                        flag = 1;
                        break;
                    }
                    if (j == str.length() - 1 && pattern.charAt(i) != str.charAt(j)) {
                        flag = 0;
                        break;
                    }
                }
            }
            if(flag == 1)
                matchedPattern.add(str);
        }
       
        return matchedPattern;
    }

- ssiddique.ms July 15, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import re

def camel_case(strings, pattern):
    splitStrings = []
    for s in strings:
        splitStrings.append(re.findall('[A-Z][a-z]*', s))
    splitPattern = re.findall('[A-Z][a-z]*', pattern)
    for ss in splitStrings:
        flag = True
        for i in xrange(len(splitPattern)):
            if i >= len(ss) or splitPattern[i] not in ss[i]:
                flag = False
                break
        if flag == True:
            print ''.join(ss)

- Anonymous July 16, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import re

def camel_case(strings, pattern):
    splitStrings = []
    for s in strings:
        splitStrings.append(re.findall('[A-Z][a-z]*', s))
    splitPattern = re.findall('[A-Z][a-z]*', pattern)
    for ss in splitStrings:
        flag = True
        for i in xrange(len(splitPattern)):
            if i >= len(ss) or splitPattern[i] not in ss[i]:
                flag = False
                break
        if flag == True:
            print ''.join(ss)

- Anonymous July 16, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import re

def camel_case(strings, pattern):
    splitStrings = []
    for s in strings:
        splitStrings.append(re.findall('[A-Z][a-z]*', s))
    splitPattern = re.findall('[A-Z][a-z]*', pattern)
    for ss in splitStrings:
        flag = True
        for i in xrange(len(splitPattern)):
            if i >= len(ss) or splitPattern[i] not in ss[i]:
                flag = False
                break
        if flag == True:
            print ''.join(ss)

- billzeng808 July 16, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int FindIndexOfChar(string str, char c, int index)
        {
            for(int i = index; i<str.Length; i++)
            {
                if(str[i] == c)
                {
                    return i;
                }
            }
            return -1;
        }

        List<String> FindMatchingStrings(List<string> stringList, string pattern)
        {
            List<string> matchingStrings = new List<string>();
            if(pattern[0].ToString() != pattern[0].ToString().ToUpper())
            {
                return matchingStrings;//invalid pattern. Return empty stringlist 
            }
            foreach (var str in stringList)
            {
                int index = 0;
                int i = 0;
                for (i = 0; i < pattern.Length; i++)
                {
                    int newIndex = FindIndexOfChar(str, pattern[i], index);
                    if (newIndex == -1)
                    {
                        break;//pattern not found. go to next string.
                    }
                    else if (i == 0 && newIndex != 0)
                    {
                        break;//goto the next string in the list.
                    }
                    else if((pattern[i].ToString() == pattern[i].ToString().ToLower()) &&
                        newIndex != index+1)
                    {
                        break;//pattern not found. go to next string.
                    }
                    index = newIndex;
                }
                if (i == pattern.Length)
                {
                    matchingStrings.Add(str);
                }
            }  
            return matchingStrings;
        }

- VamsiR July 19, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

function IsUpperCase(ch)
{
  return ch >= 'A' && ch <= 'Z';
} // IsUpperCase
	
function VerifyCCNPattern(oClassNames, sPattern)
{
  oRet = new Array();
  var nNameInx, nPatternInx
  
  for(var i=0; i<oClassNames.length; i++)
  {
    nNameInx = nPatternInx = 0
			
    if(!IsUpperCase(oClassNames[i][0]))
      continue;
				
    while( nPatternInx < sPattern.length && nNameInx < oClassNames[i].length )
    {
      if(sPattern[nPatternInx] == oClassNames[i][nNameInx])
      {
        ++nNameInx;
        ++nPatternInx;
        continue;
      }
				
      if(IsUpperCase(sPattern[nPatternInx]) && !IsUpperCase(oClassNames[i][nNameInx]))
      {
        ++nNameInx;
        continue;
      }

      break;
    } // while
			
    if(nPatternInx == sPattern.length)
      oRet.push(oClassNames[i])
  } // while
	
  return oRet;
}

- Harel Gruia July 24, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class Solution {
    
    public static void main(String [] args) {
        
        String [] words = {"HelloMars", "HelloWorld", "HelloWorldMars", "HiHo"};
        
        CamelCaseNotation ccn = new CamelCaseNotation(words);

        System.out.println(ccn.getPattern("H"));
        // TODO: it can not split HW
        System.out.println(ccn.getPattern("HW"));
        System.out.println(ccn.getPattern("Ho"));
        System.out.println(ccn.getPattern("HeWorM"));
    }
    
}

class CamelCaseNotation {
    
    private List<CamelCaseString> list;
    
    public CamelCaseNotation(String [] words) {
        this.list = new ArrayList<>();
        
        for (String str : words) {
            this.list.add(new CamelCaseString(str));
        }
    }
    
    public List<String> getPattern(String pattern) {
        List<String> results = new ArrayList<>();
        
        for (CamelCaseString ccs : list) {
            if (ccs.isMatch(pattern)) {
                results.add(ccs.getInitial());
            }
        }
        
        return results;
    }
}

class CamelCaseString {
    
    private final String [] strings;
    private final String initial;
    
    public CamelCaseString(String string) {
        this.initial = string;
        this.strings = string.split("(?<!(^|[A-Z]))(?=[A-Z])|(?<!^)(?=[A-Z][a-z])");
    }

    public String getInitial() {
        return initial;
    }
    
    public boolean isMatch(String string) {
        String [] splited = string.split("(?<!(^|[A-Z]))(?=[A-Z])|(?<!^)(?=[A-Z][a-z])");
        
        for (int i = 0; i < splited.length; i++) {
            if (i == strings.length) {
                return false;
            }
            
            if (!strings[i].startsWith(splited[i])) {
                return false;
            }
        }
        
        return true;
    }

}

- ugurdonmez87 July 25, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.ArrayList;

public class TrieNode {

	char value;
	ArrayList<TrieNode> children;
	boolean isWord;

	TrieNode(Character v) {
		value = v;
		children = new ArrayList<>();
	}

	void insert(String s) {
		if (s == null || s.length() <= 0) {
			isWord = true;
			return;
		}
		char c = s.charAt(0);
		for (TrieNode child : children) {
			if (child.value == c) {
				child.insert(s.substring(1));
				return;
			}
		}
		TrieNode newNode = new TrieNode(c);
		children.add(newNode);
		newNode.insert(s.substring(1));
	}

	void match(String prefix, String word) {
		if (prefix == null || prefix.length() <= 0) {
			getWords(word);
			return;
		}
		char c = prefix.charAt(0);
		String s=(prefix.length()>1)?prefix.substring(1):"";
		for (TrieNode child : children) {
			if (child.value == c)
				child.match(s, word + c);
		}
		if (Character.isUpperCase(c)) {
			for (TrieNode child : children) {
				if (Character.isLowerCase(child.value))
					child.match(prefix, word + child.value);
			}
		}
	}

	void getWords(String word) {

		for (TrieNode child : children) {
			if (child.isWord) {
				System.out.println(word + child.value);
			}
			child.getWords(word + child.value);
		}
	}

	public static void main(String[] args) {
		TrieNode root = new TrieNode('-');
		root.insert("HelloMars");
		root.insert("HelloWorld");
		root.insert("HelloWorldMars");
		root.insert("HiHo");
		root.match("HH", "");
	}

}

- shajibcse067@gmail.com August 01, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.ArrayList;

public class TrieNode {

	char value;
	ArrayList<TrieNode> children;
	boolean isWord;

	TrieNode(Character v) {
		value = v;
		children = new ArrayList<>();
	}

	void insert(String s) {
		if (s == null || s.length() <= 0) {
			isWord = true;
			return;
		}
		char c = s.charAt(0);
		for (TrieNode child : children) {
			if (child.value == c) {
				child.insert(s.substring(1));
				return;
			}
		}
		TrieNode newNode = new TrieNode(c);
		children.add(newNode);
		newNode.insert(s.substring(1));
	}

	void match(String prefix, String word) {
		if (prefix == null || prefix.length() <= 0) {
			getWords(word);
			return;
		}
		char c = prefix.charAt(0);
		String s=(prefix.length()>1)?prefix.substring(1):"";
		for (TrieNode child : children) {
			if (child.value == c)
				child.match(s, word + c);
		}
		if (Character.isUpperCase(c)) {
			for (TrieNode child : children) {
				if (Character.isLowerCase(child.value))
					child.match(prefix, word + child.value);
			}
		}
	}

	void getWords(String word) {

		for (TrieNode child : children) {
			if (child.isWord) {
				System.out.println(word + child.value);
			}
			child.getWords(word + child.value);
		}
	}

	public static void main(String[] args) {
		TrieNode root = new TrieNode('-');
		root.insert("HelloMars");
		root.insert("HelloWorld");
		root.insert("HelloWorldMars");
		root.insert("HiHo");
		root.match("HH", "");
	}

}

- shajibcse067 August 01, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.ArrayList;

public class TrieNode {

	char value;
	ArrayList<TrieNode> children;
	boolean isWord;

	TrieNode(Character v) {
		value = v;
		children = new ArrayList<>();
	}

	void insert(String s) {
		if (s == null || s.length() <= 0) {
			isWord = true;
			return;
		}
		char c = s.charAt(0);
		for (TrieNode child : children) {
			if (child.value == c) {
				child.insert(s.substring(1));
				return;
			}
		}
		TrieNode newNode = new TrieNode(c);
		children.add(newNode);
		newNode.insert(s.substring(1));
	}

	void match(String prefix, String word) {
		if (prefix == null || prefix.length() <= 0) {
			getWords(word);
			return;
		}
		char c = prefix.charAt(0);
		String s=(prefix.length()>1)?prefix.substring(1):"";
		for (TrieNode child : children) {
			if (child.value == c)
				child.match(s, word + c);
		}
		if (Character.isUpperCase(c)) {
			for (TrieNode child : children) {
				if (Character.isLowerCase(child.value))
					child.match(prefix, word + child.value);
			}
		}
	}

	void getWords(String word) {

		for (TrieNode child : children) {
			if (child.isWord) {
				System.out.println(word + child.value);
			}
			child.getWords(word + child.value);
		}
	}

	public static void main(String[] args) {
		TrieNode root = new TrieNode('-');
		root.insert("HelloMars");
		root.insert("HelloWorld");
		root.insert("HelloWorldMars");
		root.insert("HiHo");
		root.match("HH", "");
	}

}

- shajibcse067 August 01, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Swift 2.2

// Determines if a character is capitalized.
func isCapital(c:Character) -> Bool {
    return ("A"..."Z").contains(c)
    
}

// Splits a CamelCaseNotation string into sections.
func getSections(camelCaseString: String) -> [String] {
    var sections = [String]()
    var section = ""
    for character in camelCaseString.characters {
        if (isCapital(character)) {
            if (section.characters.count > 0) {
                sections.append(section)
                
            }
            section = String(character)
            
        } else {
            section.append(character)
            
        }
        
    }
    if (section.characters.count > 0) {
        sections.append(section)
        
    }
    return sections
    
}

// Returns an array of CamelCaseNotation strings whos prefixes match
// the CamelCaseNotation of the key.
func camelCaseNotation(words:[String], key: String) -> [String] {
    // Because SE-0003
    var words = words
    var keySections = getSections(key)
    
    for i in (0 ..< words.count).reverse() {
        var wordSections = getSections(words[i])
        
        // Remove the word if it has less sections than the key.
        if (wordSections.count < keySections.count) {
            words.removeAtIndex(i)
            continue
            
        }
        
        // Remove the word if its section doesn't match the key's corresponding section.
        for j in 0 ..< keySections.count {
            if (wordSections[j].hasPrefix(keySections[j]) == false) {
                words.removeAtIndex(i)
                break;
            }
            
        }
        
    }
    return words;
    
}

var words = ["HelloMars", "HelloWorld", "HelloWorldMars", "HiHo"]
camelCaseNotation(words, key: "H") // ["HelloMars", "HelloWorld", "HelloWorldMars", "HiHo"]
camelCaseNotation(words, key: "HW") // ["HelloWorld", "HelloWorldMars"]
camelCaseNotation(words, key: "Ho") // []
camelCaseNotation(words, key: "HeWorM") // ["HelloWorldMars"]

- helloru August 02, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void main(String args[]) {

		List<String> data = Arrays.asList("H", "HW", "Ho", "HeWorM");
		List<String> details = Arrays.asList("HelloMars", "HelloWorld", "HelloWorldMars", "HiHo");
		details.forEach(str -> {
			data.forEach(curCamCase -> {
				System.out.println(" cam case " + curCamCase + " compared to string " + str + " is "
						+ isMatchCamelCase(curCamCase, str));
			});
		});

		System.out.println("match?" + isMatchCamelCase("HelWorM", "HelloWorld"));
	}

	public static boolean isMatchCamelCase(String camelCase, String word) {
		if (camelCase.length() > 0 && word.length() == 0) {
			return false;
		}
		if (camelCase.length() == 0) {
			return true;
		}
		if (Character.isUpperCase(camelCase.charAt(0))) {
			if (Character.isUpperCase(word.charAt(0))) {
				return camelCase.charAt(0) == word.charAt(0)
						&& isMatchCamelCase(camelCase.substring(1), word.substring(1));
			} else {
				return isMatchCamelCase(camelCase, word.substring(1));
			}
		} else if (!Character.isUpperCase(camelCase.charAt(0))) {
			return camelCase.charAt(0) == word.charAt(0) && isMatchCamelCase(camelCase.substring(1), word.substring(1));
		}

		return true;
	}

- eko.harmawan.susilo August 07, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can we use RegEx?

public static void main(String[] args){

        String[] camelCaseWords = { "HelloMars", "HelloWorld", "HelloWorldMars", "HiHo" };


        String input = "HeW"; //'This is an Example';

        StringBuilder sb = new StringBuilder();
        sb.append(input.charAt(0));
        for (int i=1; i< input.length(); i++){
            char curr = input.charAt(i);
            if (curr >= 'A' && curr <= 'Z'){ //capital letter
                sb.append("[a-z]*" + curr);
            }else{
                sb.append(curr);
            }
        }
        sb.append("[a-z]*");

        for (String s : camelCaseWords){
            if (s.matches(sb.toString())){
                System.out.println(s);
            }
        }

    }

- seventhmoon August 18, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def getCamelCase(string):
    caps = range(65, 91)
    if len(string) <= 1:
        return [string]
    else:
        res = []
        pos = [i for i, x in enumerate(string) if ord(x) in caps]
        prev = 0
        for x in pos:
            if x == 0:
                continue
            res.append(string[prev:x])
            prev = x
        res.append(string[prev:])
        return res


def identify(lst, pattern):
    splits = getCamelCase(pattern)
    matched = []
    for x in lst:
        if x.startswith(splits[0]):
            matched.append(x)
    filter = []
    for y in matched:
        flag = True
        for x in splits[1:]:
            if x not in y:
                flag = False
        if flag:
            filter.append(y)
    if len(filter)==1:
        return filter[-1]
    else:
        res = []
        for z in filter:
            if len(splits)==len(getCamelCase(z)):
                res.append(z)
        if len(res)>1:
            return res
        elif len(res)==0:
            return ''
        else:
            return res[-1]






lst = ['HelloMars', 'HelloWorld', 'HelloWorldMars', 'HiHo', 'FunnyWire', 'HelloW']
pattern = 'FWi'

print identify(lst,pattern)

- deeshank September 21, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def getCamelCase(string):
    caps = range(65, 91)
    if len(string) <= 1:
        return [string]
    else:
        res = []
        pos = [i for i, x in enumerate(string) if ord(x) in caps]
        prev = 0
        for x in pos:
            if x == 0:
                continue
            res.append(string[prev:x])
            prev = x
        res.append(string[prev:])
        return res


def identify(lst, pattern):
    splits = getCamelCase(pattern)
    matched = []
    for x in lst:
        if x.startswith(splits[0]):
            matched.append(x)
    filter = []
    for y in matched:
        flag = True
        for x in splits[1:]:
            if x not in y:
                flag = False
        if flag:
            filter.append(y)
    if len(filter)==1:
        return filter[-1]
    else:
        res = []
        for z in filter:
            if len(splits)==len(getCamelCase(z)):
                res.append(z)
        if len(res)>1:
            return res
        elif len(res)==0:
            return ''
        else:
            return res[-1]






lst = ['HelloMars', 'HelloWorld', 'HelloWorldMars', 'HiHo', 'FunnyWire', 'HelloW']
pattern = 'FWi'

print identify(lst,pattern)

- ds494@njit.edu September 21, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

private static void findCamelCase(List<string> wordlist, string pattern)
{
foreach (var word in wordlist)
{
int i = 0, p = 0;

while (p<pattern.Length && i<word.Length)
{

if (word[i] == pattern[p])
{
i++;
p++;
}
else
{
while (!char.IsUpper(word[i]) && i<word.Length-1)
i++;
if (word[i] == pattern[p])
{
i++;
p++;
}
else
{
Console.WriteLine(word + " is NOT adhering to the pattern " + pattern);
break;
}
}

}

if (p == pattern.Length)
{
Console.WriteLine(word + " is adhering to the pattern " + pattern);
}

}

- Shanmuga Bharathi Nageswaran October 24, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

private static void findCamelCase(List<string> wordlist, string pattern)
        {
            foreach (var word in wordlist)
            {
                int i = 0, p = 0;
               
                    while (p<pattern.Length && i<word.Length)
                    {

                        if (word[i] == pattern[p])
                            {
                                i++;
                                p++;
                            }
                        else 
                            {
                                 while (!char.IsUpper(word[i]) && i<word.Length-1)
                                        i++;
                                    if (word[i] == pattern[p])
                                    {
                                        i++;
                                        p++;
                                    }
                                    else
                                    {
                                        Console.WriteLine(word + " is NOT adhering to the pattern " + pattern);
                                        break;
                                    }
                            }   

                    }

                if (p == pattern.Length)
                {
                    Console.WriteLine(word + " is adhering to the pattern " + pattern);
                }
                                
            }

- Shanmuga Bharathi Nageswaran October 24, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is my answer for people who are familiar with Python.

import re

inputList = ['Hello', 'HelloWorld', 'HelloWorldMars', 'HiHo', 'WorldHello']
givenString = 'HeW'

def CamelCaseNotation(inputList, givenString):
    if givenString[0].islower():
        return None
    
    # Split it based on capital letters
    splitString = re.findall(r'[A-Z][a-z]*', givenString)

    output = list()
    for item in inputList:
        splitWords = re.findall(r'[A-Z][a-z]*', item)
        # loop on the substrings of both lists at the same time
        i = 0 
        while i < min(len(splitString), len(splitWords)):
            # as long as there is a match, continue to loop
            if splitString[i] not in splitWords[i] :
                break
            i += 1
        # if all substrings of the input string match with a word from the input list, 
        # we can add this word to the output list
        if i == len(splitString) :
            output.append(item)
            
    return output
    
CamelCaseNotation(inputList, givenString)

- MLL October 31, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <string>
#include <iostream>
#include <map>

using namespace std;
struct TrieNode;

struct TrieNode {
	TrieNode* lNext[26];
	TrieNode* uNext[26];

	char ch;
	bool isWord;

	TrieNode(char c, TrieNode* p) :
		ch(c),
		lNext(),
		uNext(),
		isWord(false)
	{
	}
};

void insert(string str, TrieNode* root) {
	size_t len = str.size();
	for (size_t i = 0; i < len; ++i) {
		bool upper = str[i] >= 'A' && str[i] <= 'Z';
		TrieNode* next = NULL;
		if (upper){
			next = root->uNext[str[i] - 'A'];
			if (!next) {
				next = new TrieNode(str[i], root);
				root->uNext[str[i] - 'A'] = next;
			}
		}
		else {
			next = root->lNext[str[i] - 'a'];
			if (!next) {
				next = new TrieNode(str[i], root);
				root->lNext[str[i] - 'a'] = next;
			}
		}
		root = next;
	}

	root->isWord = true;
}

void printLeafNodes(TrieNode* cur, string str) {
	if (cur) {
		str.push_back(cur->ch);
		if (cur->isWord)
			cout << str << endl;

		for (int i = 0; i < 26; ++i) {
			if (cur->lNext[i])
				printLeafNodes(cur->lNext[i], str);

			if (cur->uNext[i])
				printLeafNodes(cur->uNext[i], str);
		}
	}
}

void findMatches(string pat, size_t index, TrieNode* cur, string res) {
	if (index >= pat.size())
		return;
	char c = pat[index];
	bool upper = c >= 'A' && c <= 'Z';
	int cIndex = upper
		? c - 'A'
		: c - 'a';

	TrieNode* next = upper
		? cur->uNext[cIndex]
		: cur->lNext[cIndex];

	if (next) {
		if (index == pat.size() - 1)
			printLeafNodes(next, res);
		else{
			res.push_back(c);
			findMatches(pat, index + 1, next, res);
		}
	}
	else{
		if (upper) {
			for (int i = 0; i < 26; ++i) {
				if (cur->lNext[i]) {
					res.push_back(cur->lNext[i]->ch);
					findMatches(pat, index, cur->lNext[i], res);
				}
			}
		}
	}
}

void main2() {
	TrieNode* root = new TrieNode(NULL, NULL);
	string arr[] = { "HelloMars", "HelloWorld", "HelloWorldMars", "HiHo" };
	for (int i = 0; i < 4; ++i)
		insert(arr[i], root);

	string pat[] = { "H", "HW", "Ho", "HeWorM" };
	for (int i = 0; i < 4; ++i){
		cout << "Matches for " << pat[i] << ":" << endl;
		findMatches(pat[i], 0, root, "");
		cout << endl;
	}
}

- malcolm.carvalho September 10, 2017 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More