check string end among a list of strings
Hello,
I need to write a function that checks the end of a string among a list of strings. I don't want to know which string matches, I just need a true/false value to tell me whether any string matches or not.
First, I tried to call the fucntion String.endsWith() with each one separately. Then, I used the Patten, Matcher classes to check against regular expression in the form ".*("+end1+"|"+end2+"|"+...+"|"+endx+")". It worked well but it was much slower. Do I need to write a complete algorithm by my self, or there is a fast method in java that will do the work for me?
> Hello,
> I need to write a function that checks the end of a
> a string among a list of strings. I don't want to
> know which string matches, I just need a true/false
> value to tell me whether any string matches or not.
> First, I tried to call the fucntion
> on String.endsWith() with each one separately. Then,
> I used the Patten, Matcher classes to check against
> regular expression in the form
> ".*("+end1+"|"+end2+"|"+...+"|"+endx+")". It worked
> well but it was much slower. Do I need to write a
> complete algorithm by my self, or there is a fast
> method in java that will do the work for me?
try
"^.*"+end1+"$|^.*"+end2+"$|^.*"+...+"$|^.*"+endx+"$"
It may improve the performance
This Trie is what I thought of.
Actually I built it before I read this reply as I was in a hurry (I named it TestTree).
Mine is better in that it does not have to inverse strings as it is build in from rear to start of string.
I will try it anyway because it may be better.
Thank you all.
Here's my implementation
- TreeNode.java --
import java.util.LinkedHashMap;
class TreeNode<V> extends LinkedHashMap<Character,TreeNode><V>> {
public V value;
public TreeNode() {
super();
}
public TreeNode(V value) {
super();
this.value = value;
}
}
--
TestTree.java --
import java.util.Collection;
/**
* Builds a tree that has a character over each branch,
* and tests a string if it has a path in this tree.
* We add strings and check them in reverse order because
* this is what we need from it.
* @author Ahmed Saad
*/
@SuppressWarnings("unchecked")
public class TestTree {
/**The root node of the TestTree.*/
private TreeNode<?> root;
/**
* Builds an empty tree
*/
public TestTree() {
root = new TreeNode();
}
/**
* Adds the given String to the TestTree.
* It checks character one by one starting from the end,
* it adds nodes in the tree so that there is a path from the root with the given string
* @param s the string to be added
*/
public void add(String s) {
TreeNode<?> p = root;
for (int i=s.length()-1;i>=0;i--) {
char c = s.charAt(i);
TreeNode q = p.get(c);
if (q==null) {
q = new TreeNode();
p.put(c,q);
}
p = q;
}
}
/**
* Add all given strings to the tree using {link #add(String)}
* @param cs
*/
public void addAll(Collection<String> cs) {
for (String s:cs)
add(s);
}
/**
* Checks the given String in the TestTree.
* It checks character of the string one bye one starting from the rear.
*
* @param s the string to be checked
*/
public boolean contains(String s) {
TreeNode<?> p = root;
int i=s.length();
while (--i>=0) {
//get next character
char c = s.charAt(i);
//get the child node under the next character
TreeNode<?> q = p.get(c);
//no branch with this character
if (q==null)
return false;
//if this is a leaf node, we have finished
if (q.isEmpty())
return true;
p=q;
}
return false;
}
public static void main(String args[]) {
TestTree tt = new TestTree();
tt.add("er");
tt.add("or");
tt.add("ion");
tt.add("ed");
System.err.println(tt.contains("ionor"));
}
}
