regex - 数字范围的正则表达式生成器

Question

我查看了stackExchange的描述，算法题是允许的题目之一。就这样吧。

给定一个范围的输入，其中开始和结束数字具有相同的数字位数(比如 2、3 或 4)，我想编写代码来生成一组正则表达式，当对照反过来，告诉我这个数字是否在原来的范围内。

例如:如果范围是145-387，那么146、200、280都会匹配生成的正则表达式之一，144、390(习惯说290)、445(习惯说345)不会。

我一直认为结果会是一个正则表达式列表，例如:

14[5-9]             // match 145-149
1[5-9]0-9]          // 150-199
2[0-9][0-9]         // 200-299
3[0-7][0-9]         // 300-379
38[0-7]             // 380-387

然后检查号码的软件将测试被测试的 3 位数代码是否与其中任何一个匹配。

那么生成表达式集的最佳方法是什么？

我想出的最新(在一个系列中)是:

1. 确定两个范围号不同的第一个数字(1145-1158，第一个不同的数字是第三个)
2. 对于不同的数字，确定它们的第一个数字是否相差不止一个——如果是，则该范围有自己的正则表达式(在我们的示例中为 200-299)
3. 要获得较低的范围:对于每个其他数字:以范围开头的第一个数字为前缀，将数字递增一个，用 0 填充到相同的长度，并与具有 9 的数字配对在数字位置和所有填充位置。在我们的示例中，将 4 递增到 5，填充得到 150，生成正则表达式来处理 150-199。
4. 要获得更高的范围:对于每个其他数字:以范围末尾的第一个数字为前缀，将数字递减一个，用 0 填充其余部分，在所有填充 0 的位置和递减的数字中与一个带有 9 的数字配对数字。在我们的示例中，正则表达式处理 300-379。

我错过了什么吗？甚至在上面也有一些我正在掩盖的细节，这似乎可以从算法剑中砍掉细节中获益。但我想出的其他事情比这更困惑。

Answer 1

这是我的解决方案和复杂度为 O(log n) 的算法(n 是范围的末尾)。我相信这是这里最简单的一个:

基本上，将您的任务分成以下步骤:

1. 逐渐“削弱”范围的开始。
2. 逐渐“弱化”范围的end。
3. 合并这两者。

所谓“弱化”，我的意思是找到可以用这个特定数字的简单正则表达式表示的范围的末端，例如:

145 -> 149,150 -> 199,200 -> 999,1000 -> etc.

这是一个反向的，对于范围的 end:

387 -> 380,379 -> 300,299 -> 0

合并是注意到 299->0 和 200->999 的重叠并将它们组合成 200->299 的过程。

结果，您将得到这组数字(第一个列表完整，第二个倒置:

145, 149, 150, 199, 200, 299, 300, 379, 380, 387

现在，这是有趣的部分。成对获取数字，并将它们转换为范围:

145-149, 150-199, 200-299, 300-379, 380-387

或者在正则表达式中:

14[5-9], 1[5-9][0-9], 2[0-9][0-9], 3[0-7][0-9], 38[0-7]

weakening 的代码如下所示:

public static int next(int num) {
    //Convert to String for easier operations
    final char[] chars = String.valueOf(num).toCharArray();
    //Go through all digits backwards
    for (int i=chars.length-1; i>=0;i--) {
        //Skip the 0 changing it to 9. For example, for 190->199
        if (chars[i]=='0') {
            chars[i] = '9';
        } else { //If any other digit is encountered, change that to 9, for example, 195->199, or with both rules: 150->199
            chars[i] = '9';
            break;
        }
    }

    return Integer.parseInt(String.valueOf(chars));
}

//Same thing, but reversed. 387 -> 380, 379 -> 300, etc
public static int prev(int num) {
    final char[] chars = String.valueOf(num).toCharArray();
    for (int i=chars.length-1; i>=0;i--) {
        if (chars[i] == '9') {
            chars[i] = '0';
        } else {
            chars[i] = '0';
            break;
        }
    }

    return Integer.parseInt(String.valueOf(chars));
}

剩下的就是技术细节，很容易实现。下面是这个 O(log n) 算法的实现:https://ideone.com/3SCvZf

哦，顺便说一下，它也适用于其他范围，例如范围 1-321654 结果是:

[1-9]
[1-9][0-9]
[1-9][0-9][0-9]
[1-9][0-9][0-9][0-9]
[1-9][0-9][0-9][0-9][0-9]
[1-2][0-9][0-9][0-9][0-9][0-9]
3[0-1][0-9][0-9][0-9][0-9]
320[0-9][0-9][0-9]
321[0-5][0-9][0-9]
3216[0-4][0-9]
32165[0-4]

129-131 是:

129
13[0-1]