sid
BAN USERint searchInSorted(int arr[],int val, int start,int end)
{
if(start>=end)
return -1;
int mid=(start+end-1)/2;
if(arr[mid]==val)
return mid;
if(arr[mid]<val)
searchInSorted(arr,val,mid+1,end);
else
searchInSorted(arr,val,start,mid);
}
int searchInSorted(int arr[],int val,int size)
{
int pos = searchInSorted(arr,val,0,size);
int tmp=pos;
while(arr[tmp]==val&&tmp>=0)
tmp--;
return tmp+1;
}
Solution with trie as dictionary
class Trie
{
public:
Trie():root(NULL){}
Node* root;
int searchInNode(Node* root, char ch)
{
if (!root)
return -1;
int size = root->next.size();
if(size==0)
return -1;
for(int i=0;i<size;i++)
{
if(root->next[i]->ch==ch)
return i;
}
return -1;
}
void push(Node* node, string &str,int pos)
{
if(pos == str.size())
{
node->end=true;
return;
}
if(!node)
return;
int i = searchInNode(node,str[pos]);
if (i>=0)
{
push(node->next[i],str,pos+1);
}
else
{
Node* newNode = new Node;
newNode->ch=str[pos];
node->next.push_back(newNode);
push(newNode,str,pos+1);
}
}
void Insert(string str)
{
if(!root)
root = new Node;
push(root,str,0);
}
bool matchNode(Node* node,string& str, int pos)
{
if(NULL == node)
return false;
if (pos == str.size())
{ if (node->end)
return true;
else
return false;
}
int i=searchInNode(node,str[pos]);
if(i>=0)
return matchNode(node->next[i],str,pos+1);
else
return false;
}
bool match(string str)
{
return matchNode(root,str,0);
}
int matchRow(Node* node,char ch[][3],int M,int N,int start)
{
if (!node)
return start;
if(start==N)
return start-1;
int i = searchInNode(node,ch[M][start]);
if(i>=0)
return matchRow(node->next[i],ch,M,N,start+1);
else
return start-1;
}
int matchCol(Node* node,char ch[][3],int M,int N,int start)
{
if (!node)
return start;
if(start==M)
return start-1;
int i = searchInNode(node,ch[start][N]);
if(i>=0)
return matchRow(node->next[i],ch,M,N,start+1);
else
return start-1;
}
void matchRow(char ch[][3],int M,int N)
{
for(int row=0;row<M;row++)
for(int col=0;col<N;col++)
{
int matlen=matchRow(root,ch,row,N,col);
for(int i=col;i<=matlen;i++)
cout<<ch[row][i];
}
}
void matchCol(char ch[][3],int M,int N)
{
for(int col=0;col<N;col++)
for(int row=0;row<M;row++)
{
int matlen=matchCol(root,ch,M,col,row);
for(int i=col;i<=matlen;i++)
cout<<ch[i][col];
}
}
};
void main ()
{
Trie trie;
trie.Insert("cat");
trie.Insert("god");
trie.Insert("go");
trie.Insert("dog");
trie.Insert("do");
trie.Insert("boa");
char arr[3][3]={'c','a','t','g','o','d','f','b','r'};
trie.matchRow(arr,3,3);
trie.matchCol(arr,3,3);
}
#include <stack>
using namespace std;
class Node
{
public:
char data;
Node* next;
Node():next(NULL){}
};
bool findPalindrome(Node* root)
{
if(!root)
return false;
Node* t1=root;
Node* t2=root;
stack<char> st;
bool end=false;
//bool odd=false;
while (true)
{
if (t1==NULL)
break;
if(!end)
{
st.push(t1->data);
}
else
{
char ch = st.top();
if(t1->data!=ch)
return false;
st.pop();
}
if(t1)
t1=t1->next;
if(t2)
{
t2=t2->next;
if(t2)
t2=t2->next;
else
{
st.pop();
}
}
if(!t2)
{
end=true;
}
}
return true;
}
class Node
{
public:
int data;
Node *next;
};
Node* findCyclic(Node* root)
{
Node* t1=root;
Node* t2=root;
while(t1!=NULL&&t2!=NULL)
{
t1=t1->next;
t2=t2->next;
if(t2)
t2=t2->next;
if(t1==t2)
return t1;
}
return NULL;
}
Node* findCollison(Node* root)
{
Node* loop=findCyclic(root);
if(!loop)
return NULL;
Node* t1=root;
while(loop!=t1)
{
loop = loop->next;
t1=t1->next;
}
return loop;
}
void mergeArray(int result[], int arr1[],int size1,int arr2[],int size2)
{
int length=size1+size2;
int c=0,c1=0,c2=0;
while (c1!=size1||c2!=size2)
{
if(c1==size1&&c2!=size2)
{
result[c++]=arr2[c2++];
}
if(c2==size2&&c1!=size1)
{
result[c++]=arr1[c1++];
}
if(c1!=size1&&c2!=size2)
{
if(arr1[c1]<arr2[c2])
result[c++]=arr1[c1++];
else
result[c++]=arr2[c2++];
}
}
}
- sid June 02, 2013