kingKode
BAN USERpackage com.careercup.practice;
public class LongestCommonString {
String LCS(String a , String b)
{
if(a.length() == 0 || b.length() == 0)
{
return "";
}
String op1 = (a.charAt(0) == b.charAt(0) ? a.charAt(0) : "") + LCS(a.substring(1), b.substring(1)) ;
String op2 = (a.charAt(0) == b.charAt(0) ? a.charAt(0) : "") + LCS(a.substring(0), b.substring(1));
String op3 = (a.charAt(0) == b.charAt(0) ? a.charAt(0) : "") + LCS(a.substring(1), b.substring(0)) ;
if(op1.length() > op2.length() && op1.length() > op3.length())
return op1;
else if(op2.length() > op1.length() && op2.length() > op3.length())
return op2;
else
return op3;
}
public static void main(String[] args) {
LongestCommonString lcs = new LongestCommonString();
System.out.println(lcs.LCS("Bangalore", "Mysore"));
}
}
The approach is simple:
match the head and for the tail do a swap for desired character to left.
I could not prove it would be lease
#include <iostream>
#include <map>
#include <cstring>
using namespace std;
void swap(char * convert , int j)
{
char temp = convert[j];
convert[j] = convert[j-1];
convert[j-1] = temp;
}
int transformCost(char * master, char * convert , int i)
{
int matchcounter = 0;
int cost = 0;
while(matchcounter < i)
{
if(master[matchcounter] == convert[matchcounter])
{
matchcounter++;
continue;
}
char m = master[matchcounter];
bool found = false;
int matchpos = -1;
for(int j = matchcounter ; j < i; j++)
{
if(convert[j] == m)
{
matchpos = j;
found = true;
break;
}
}
if(found)
{
swap(convert,matchpos);
cost++;
}
else
{
return -1;
}
}
cout<<"Master : " << master<<endl;
cout<<"Convert : " << convert<<endl;
return cost;
}
int main()
{
char a[] = "101010101010";
char b[] = "111111000000";
cout<<transformCost(a,b, strlen(a))<<endl;
return 0;
}
set<int> getMissing(int* input, int low, int high, int missing)
{
static set<int> result;
static int calls = 0;
calls++;
if (low > high || low < 0 || high < 0 || result.size() == missing)
return result;
if (low + 1 == high || low == high )
{
int temp = input[low] + 1;
while (temp < input[high])
{
result.insert(temp);
temp++;
}
//check lower boundary
if (low > 0)
{
int temp1 = input[low - 1];
while (temp1 + 1 < input[low])
{
result.insert(temp1 + 1);
temp1++;
}
}
//check upper boundary
int temp2 = input[high];
while (temp2 + 1 < input[high+1])
{
result.insert(temp2 + 1);
temp2++;
}
}
unsigned int mid = (low + high) / 2;
//both half sets missing a number
if (input[mid] != mid && mid >= 2)
{
getMissing(input, low, mid-1, missing);
getMissing(input, mid+1, high, missing);
}
return result;
}
Try This:
a) Lets say we want to track top n numbers, init all top n to 0 with freq 0;
b) Do a linear Pass on array:
1) for a number if its >= the top n numbers you know so far , start matching it with your top n numbers,
1.a) it it matches any increase frq count and continue;
1.b) if its greater than a top n, insert it and shift other top n down
2) Print in required format.
- kingKode April 04, 2015