Google Interview Question
Country: United States
Interview Type: Phone Interview
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;
}
}
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')
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);
}
}
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);
}
}
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);
}
}
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;
}
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
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;
}
}
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)];
}
}
}
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)
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);
}
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;
}
}
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
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
#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;
}
#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;
}
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;
}
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;
}
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;
}
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;
}
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)
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)
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)
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;
}
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;
}
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;
}
}
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", "");
}
}
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", "");
}
}
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", "");
}
}
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"]
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;
}
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);
}
}
}
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)
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)
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);
}
}
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);
}
}
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)
#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;
}
}
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.
- Johnie July 08, 2016