javascript - 在较大的字符串中查找包含给定字母集的最小子字符串

Question

假设您有以下字符串:

FJKAUNOJDCUTCRHBYDLXKEODVBWTYPTSHASQQFCPRMLDXIJMYPVOHBDUGSMBLMVUMMZYHULSUIZIMZTICQORLNTOVKVAMQTKHVRIFMNTSLYGHEHFAHWWATLYAPEXTHEPKJUGDVWUDDPRQLUZMSZOJPSIKAIHLTONYXAULECXXKWFQOIKELWOHRVRUCXIAASKHMWTMAJEWGEESLWRTQKVHRRCDYXNT
LDSUPXMQTQDFAQAPYBGXPOLOCLFQNGNKPKOBHZWHRXAWAWJKMTJSLDLNHMUGVVOPSAMRUJEYUOBPFNEHPZZCLPNZKWMTCXERPZRFKSXVEZTYCXFRHRGEITWHRRYPWSVAYBUHCERJXDCYAVICPTNBGIODLYLMEYLISEYNXNMCDPJJRCTLYNFMJZQNCLAGHUDVLYIGASGXSZYPZKLAWQUDVNTWGFFY
FFSMQWUNUPZRJMTHACFELGHDZEJWFDWVPYOZEVEJKQWHQAHOCIYWGVLPSHFESCGEUCJGYLGDWPIWIDWZZXRUFXERABQJOXZALQOCSAYBRHXQQGUDADYSORTYZQPWGMBLNAQOFODSNXSZFURUNPMZGHTAJUJROIGMRKIZHSFUSKIZJJTLGOEEPBMIXISDHOAIFNFEKKSLEXSJLSGLCYYFEQBKIZZTQQ
XBQZAPXAAIFQEIXELQEZGFEPCKFPGXULLAHXTSRXDEMKFKABUTAABSLNQBNMXNEPODPGAORYJXCHCGKECLJVRBPRLHORREEIZOBSHDSCETTTNFTSMQPQIJBLKNZDMXOTRBNMTKHHCZQQMSLOAXJQKRHDGZVGITHYGVDXRTVBJEAHYBYRYKJAVXPOKHFFMEPHAGFOOPFNKQAUGYLVPWUJUPCUGGIXGR
AMELUTEPYILBIUOCKKUUBJROQFTXMZRLXBAMHSDTEKRRIKZUFNLGTQAEUINMBPYTWXULQNIIRXHHGQDPENXAJNWXULFBNKBRINUMTRBFWBYVNKNKDFR

我试图找到包含字母 ABCDA 的最小子字符串。

我尝试了正则表达式方法。

console.log(str.match(/[A].*?[B].*?[C].*?[D].*?[A]/gm).sort((a, b) => a.length - b.length)[0]);

这行得通，但它只能找到 ABCDA 出现的字符串(按该顺序)。这意味着它不会找到字母按如下顺序出现的子字符串:BCDAA

我正在尝试更改我的正则表达式来解决这个问题。如果不使用 | 并输入所有不同的情况，我将如何做到这一点？

Answer 1

你不能。

让我们考虑一种特殊情况:假设您要查找的字母是A、A 和B。在你的正则表达式中的某个点肯定会有一个 B。但是，B 左右两部分是相互独立的，因此不能相互引用。 B 右侧的子表达式中匹配了多少个 A 取决于左侧部分中已匹配的 A 的数量.这对于正则表达式是不可能的，因此您必须展开所有不同的订单，订单可能很多!

另一个说明该问题的流行示例是匹配左括号和右括号。不可能编写正则表达式断言在给定字符串中，左括号序列后跟相同长度的右括号序列。这样做的原因是，与有限状态机相比，要计算括号，您需要堆栈机，但正则表达式仅限于可以使用 FSM 匹配的模式。