O(ren) :)
BAN USERrecursive solution.
public static boolean isMatch(String regex, String sentence) {
if (regex.isEmpty()) {
return true;
}
if (regex.charAt(0) == '.') {
// if sentence is not empty match and continue to next character
return (!sentence.isEmpty() && isMatch(regex.substring(1),
sentence.substring(1)));
}
// it must be a letter since the code skips *
if (regex.length() > 1 && regex.charAt(1) == '*') {
// lets try to skip this char
if (isMatch(regex.substring(2), sentence)) {
return true;
}
}
// no match with out the current letter lets try with it
if (sentence.isEmpty() || !(regex.charAt(0) == sentence.charAt(0))) {
return false;
}
return isMatch(regex.substring(1), sentence.substring(1));
}
This is Java solution with running complexity of O(2n) = O(n)
and space complexity of O(2n) = O(n)
I might lower to space complexity to only one extra array but the solution will be less clean.
public static int[] removeKDuplicates(int[] list, int k)
{
// i use ArrayList because the final size is unknown
ArrayList<Integer> newList = new ArrayList<Integer>();
int counter = 0;
// since the integers are positive -1 must be unique
int prev = -1;
for (int current : list)
{ if ( prev == current )
{
++counter;
if ( counter >= k)
{
continue;
}
}else
{
counter = 0;
prev = current;
}
newList.add(current);
}
// copy the Array to int[]
int[] returnedList = new int[newList.size()];
for (int i = 0; i < returnedList.length ; i++)
{
returnedList[i] = newList.get(i);
}
return returnedList;
}
Repammiwilson5, Personnel at BMO Harris Bank
Hi I am Ammy from Served on a research team for improved customer satisfaction survey process,Moderated focus groups to ...
RepPatriciaNRowe, Consultant at ADP
Hi i am a Freelance Writer and Social Media Manager who helps finance professionals and Fin-tech startups build an audience ...
Nice and clean
- O(ren) :) January 25, 2015