pisaruk
BAN USERTaking into account that we are dealing with prefix matching we could use a Trie as pointed out by @zahidbuet106 or we could use a DFA and not a NFA(this is required only if we are going to deal with suffixes, patterns like: .*1234). This would require less space.
- pisaruk February 15, 2013public static Node search(Node node, int value) {
while (node != null && node.getValue() != value) {
if (value > node.getValue())
node = node.getRigth();
else
node = node.getLeft();
}
return node;
}
public static Node findNode(Node node, int value) {
Node _node = node;
if (node.getValue() != value) {
Node current = node;
while (current.getParent() != null) {
current = current.getParent();
}
_node = search(current, value);
}
if (_node == null)
return null;
if (_node.getRigth() != null) {
return min(_node.getRigth());
} else {
Node current = _node;
Node parent = current.getParent();
while (parent != null && parent.getRigth() == current) {
current = parent;
parent = parent.getParent();
}
return parent;
}
}
public static Node min(Node node) {
if (node == null)
return null;
Node cur = node;
while (cur.getLeft() != null)
cur = cur.getLeft();
return cur;
}
O(log(n)) complexity.
- pisaruk February 14, 2013First of all I cannot aasume from the problem statement that we are dealing with prefix or suffixes, so I think we could imagine that any check number containing any pattern would be considered a fraud.
Taking this into account, we could apply String matching with finite automata instead of using a Trie. If the automata accepts the string we are done. The running time, without the automata construction preprocessing, is Θ(k) where k is the length of the input to be checked. Neither Trie nor DAFSA provides O(1) running time and the Hash solution proposed by JerryC do not work for suffixes or prefixes because it will only match the exact string.
If we are dealing with undirected graphs there is a solution with O(V) complexity, we need to check that the graph is a forest, otherwise it will have cycle.
- pisaruk February 15, 2013For a Directed Graph a simple DFS would reveal a cycle if we found a back node during the execution. The complexity would by O(V + E).