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

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是相互独立的，因此您不能从一个部分引用另一个部分。A右侧子表达式中匹配的 s数量B取决于A左侧部分中已匹配的 s 数量。这对于正则表达式来说是不可能的，因此您必须展开所有不同的订单，数量可能很多！

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