Java regular expression to match a lexicographical range of strings

Question

I have looked through all kinds of Java REGEX information and have not found the answer I'm looking for:

How do I find all Strings that are between two values (abc and def)?

So if I have the following strings:

abc
acc
ace
amf
def
efg
khp
mlo

I would hope to get the following because these are between abc and def (including):

abc 
acc
ace
amf
def

»between« in the sense of »a substring with `abc` to the left and `def` to the right« or »between« in a lexicographic odering? — Joey, Jun 27 '11 at 13:37
@Jarrod, wow, you took the liberty of clarifying the question radically :P — aioobe, Jun 27 '11 at 13:45
The input strings are a sequence of separate inputs or a single text file with newline delimiters? Should the output be a list of single blocks of text or a list of separate strings? Should this cope with multiple "abc" and "def" markers? Should this cope with overlapping "abc" and "def" markers? — Alan Escreet, Jun 27 '11 at 13:47
@aioobe I just reformatted it data they way it was **intended to be** viewed the poster didn't know how to format it, they had it in a vertical list but it wasn't showing up that way. stackoverflow is a community site, that is why everyone has the ability to edit everything, to help make things better for everyone. — , Jun 27 '11 at 13:49
@aioobe that is a clarification of the posters intent that they didn't express clearly as seen in the answers that are incorrect because they didn't read for comprehension, the expected output shows this clearly. — , Jun 27 '11 at 15:12
@Jarrod Roberson: No the expected output is directly in line with the provided input being prevously lexicographically sorted and provided already in order. The post did not originally indicate that the order would not be sorted when provided for matching. That was an assumption the turns out to be correct. However, it was an assumption. — Bueller, Jun 27 '11 at 15:31

score 9 · Answer 1 · edited May 23 '17 at 12:24

Using regular expressions (not recommended)

There is no direct way of expressing this. It is in fact almost identical to figuring out if a given number is within a specific range. (That is, providing a regular expression matching digits within the range 123-456.)

You can "encode" it with a fairly complex regular expression though. A process which I've described here:

How to generate a regular expression at runtime to match a numeric range

For the specific example of "abc" to "def" you would write it like this:

a followed
- b followed by c-z, or
- c-z followed by any character, or
b-c followed by any two characters, or
d followed by
- a-d followed by any character, or
- e followed by
  - a-f.

Here it is in code:

String pattern = "a(b[c-z]|[c-z][a-z])|[bc][a-z][a-z]|d([a-d][a-z]|e[a-f])";

for (String s: "abc acc ace amf def efg khp mlo".split(" "))
    System.out.println(s + (s.matches(pattern) ? " matches" : ""));

Output:

abc matches
acc matches
ace matches
amf matches
def matches
efg
khp
mlo

Using `String.compareTo` (recommended)

You should consider comparing the strings instead:

"abc".compareTo(s) <= 0 && s.compareTo("def") <= 0

Example:

String lower = "abc", upper = "def";

for (String s: "abc acc ace amf def efg khp mlo".split(" ")) {
    boolean match = lower.compareTo(s) <= 0 && s.compareTo(upper) <= 0;
    System.out.println(s + (match ? " matches" : ""));
}

Output:

abc matches
acc matches
ace matches
amf matches
def matches
efg
khp
mlo

As I have said before, I am probably going to hell for posting links to this [RegEx utility for calculating number ranges](http://utilitymill.com/utility/Regex_For_Range), you can do ranges in RegEx, you **shouldn't** it is completely un-maintainable and criminal to make someone come behind you to modify this, but it is possible. Just doing a `compare` in a Turing-complete language is your best option. — , Jun 27 '11 at 13:29
Correction: `a(b[c-z]|[c-z][a-z])|[bc][a-z][a-z]|d([a-d][a-z]|e[a-f])` (yours incorrectly matches `aaa` to `abb`). But +1 anyway, for the `compareTo()` solution. ;) — Alan Moore, Jun 27 '11 at 14:49

score 2 · Answer 2 · answered Jun 27 '11 at 13:40

Are you looking for something like this? (Interpreting "between" as lexical ordering and not as placement within a parent String)

public static boolean between(
    final String candidate, final String left, final String right) {
      return left.compareTo(candidate) <= 0 && candidate.compareTo(right) <= 0;
}

Test code:

public static void main(final String[] args) throws Exception {
    final String[] words = "abc acc ace amf def efg khp mlo".split("\\W+");
    final String left = "abc";
    final String right = "def";
    for (final String word : words) {
        System.out.println(MessageFormat.format("{0}{1}between {2} and {3}",
        word, (between(word, left, right) ? " is " : " is not "), left, right));
    }
}

Output:

abc is between abc and def
acc is between abc and def
ace is between abc and def
amf is between abc and def
def is between abc and def
efg is not between abc and def
khp is not between abc and def
mlo is not between abc and def

Java regular expression to match a lexicographical range of strings

2 Answers2

Using regular expressions (not recommended)

Using String.compareTo (recommended)

Using `String.compareTo` (recommended)