jellyenigma
BAN USERpublic Set<String> findRepeatedSubString(String s,int length){
if(s==null||s.length()==0) return null;
Set<String> checkSet = new HashSet<String>();
Set<String> result = new TreeSet<String>();
for(int i=0;i<s.length()-length+1;i++){
if(!checkSet.contains(s.substring(i,i+length)))
checkSet.add(s.substring(i,i+length));
else
result.add(s.substring(i,i+length));
}
if(result.size()==0) return null;
return result;
}
- jellyenigma February 03, 2014why didn't anyone mention that the queue could be a memory concern if it has unlimited children since BFS is preparing children nodes in the queue while it's visiting the nodes on current level?
- jellyenigma January 01, 2014With no parent link, it has to use extra memory. Stack or linked list to track the order.
With parent link, we can divide it into 2 cases.
a) the current iterator has right subtree. the next node is the leftmost node in this right subtree.
b) the current iterator has no right subtree, go up to ancestor's node. UNTIL
if the ancestor node is left child of it's parent's node, that ancestor's parent node is the next node.
why not?
we can use pre-fix tree to implement this.
1) construct empty pre-fix trie in every insert operation
2) find the node in the trie which contains the last character of the substring
3) execute DFS and store all the leaf nodes under that node.
root->right=constructTree(preorder,startPre+rootIndex-startIn+1,endPre,inorder,rootIndex+1,endPre);
//--> it should be
root->right=constructTree(preorder,startPre+rootIndex-startIn+1,endPre,inorder,rootIndex+1,inPre);
My attempt:
using modified BFS and linkedList like a queue.
keep tracking the level number.
always return all nodes in certain level(excluding the target node) if target node is found.
public List<Node> findCousins(Node root,Node src){
if(root==null) return null;
List<Node> q = new LinkedList<Node>();
q.add(root);
int curLevl=0,nodesNoOnCurLevel=1,nodesNoOnNextLevel=0;
boolean isFound=false;
List<Node> cousinsQueue = new LinkedList<Node>();
while(q.size()!=0){
Node curNode = q.remove(0);// acts like dequeue
nodesNoOnCurLevel--; // decrement number of nodes on current level
if(curNode==src){
isFound=true;
}
else
cousinsQueue.add(curNode);
if(curNode.left!=null){
q.add(curNode.left);
nodesNoOnNextLevel++; // increment number of nodes on next level
}
if(curNode.right!=null){
q.add(curNode.right);
nodesNoOnNextLevel++; // increment number of nodes on next level
}
if(nodesNoOnCurLevel==0){
if(isFound==true)
return cousinsQueue;
else{
nodesNoOnCurLevel=nodesNoOnNextLevel;
nodesNoOnNextLevel=0;
curLevl++;
}
}
}
return null;
}
}
- jellyenigma February 03, 2014