logo标签列表

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

javascriptregexstringsubstring
5

假设您有以下字符串：

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这样字母顺序不同的子字符串。

我想改变我的正则表达式以解决这个问题。如何在不使用|并且不列出所有不同情况的情况下实现？

你的意思是说“ABCZZAD”如果是最短的话就可以吗？你想要包含B、C、D和两个A的字符串中最小的部分？ - miguel-svq
@miguel-svq 是的 - 没错 - Nilzone-
可能是重复的问题 https://dev59.com/yGw05IYBdhLWcg3w_W1O - גלעד ברקן
2
我不认为这是一个重复的问题，但肯定很接近并且是某种子情况。S是字符串，但不想找到所有元素，只想找到S元素的一个子集。乍一看，这似乎是一个简单的问题，但实际上并不是。（而且不知道如何用正则表达式高效地解决它） - miguel-svq
你需要一个非常高效的解决方案还是只需要“能用”的东西？我的意思是：实际字符串有多长，这些集合中有多频繁需要“查找”，它需要多实时等等。 - miguel-svq
显示剩余3条评论
4个回答
3
你做不到。
让我们考虑一个特殊情况：假设你要查找的字母是A、A和B。在你的正则表达式中，肯定会有一个B。然而，B左侧和右侧的部分是独立的，所以你无法从一个部分引用到另一个部分。右侧子表达式中匹配的A的数量取决于左侧已经匹配的A的数量。这在正则表达式中是不可能的，因此你必须展开所有不同的顺序，这可能很多！
另一个常见的例子是匹配开放括号和闭合括号。不可能编写一个正则表达式，断言在给定的字符串中，一串开放括号后面跟随着相同长度的闭合括号序列。原因是要计数括号，需要一个堆栈机而不是有限状态机，但正则表达式仅限于使用FSM可以匹配的模式。
1
好吧...他不能“只用正则表达式”。 正则表达式一直是他的第一种方法，但这并不是问题的条件。;) - miguel-svq
1
我理解他正在尝试使用正则表达式来完成这个任务：“我正在尝试更改我的正则表达式以考虑这一点。我该怎么做[...]” - lex82
我现在的代码只能处理 ABCDA 这个顺序出现的情况，我本以为可以修改一下让它能够处理所有可能的顺序，但你说得对 :) - Nilzone-
不幸的是，我所看到的唯一解决方案是生成一个包含所有可能顺序的正则表达式。 - lex82
1
这个算法没有使用正则表达式，但是也找到了两个解决方案。
var haystack = 'FJKAUNOJDCUTCRHBYDLXKEODVBWTYPTSHASQQFCPRMLDXIJMYPVOHBDUGSMBLMVUMMZYHULSUIZIMZTICQORLNTOVKVAMQTKHVRIFMNTSLYGHEHFAHWWATLYAPEXTHEPKJUGDVWUDDPRQLUZMSZOJPSIKAIHLTONYXAULECXXKWFQOIKELWOHRVRUCXIAASKHMWTMAJEWGEESLWRTQKVHRRCDYXNTLDSUPXMQTQDFAQAPYBGXPOLOCLFQNGNKPKOBHZWHRXAWAWJKMTJSLDLNHMUGVVOPSAMRUJEYUOBPFNEHPZZCLPNZKWMTCXERPZRFKSXVEZTYCXFRHRGEITWHRRYPWSVAYBUHCERJXDCYAVICPTNBGIODLYLMEYLISEYNXNMCDPJJRCTLYNFMJZQNCLAGHUDVLYIGASGXSZYPZKLAWQUDVNTWGFFYFFSMQWUNUPZRJMTHACFELGHDZEJWFDWVPYOZEVEJKQWHQAHOCIYWGVLPSHFESCGEUCJGYLGDWPIWIDWZZXRUFXERABQJOXZALQOCSAYBRHXQQGUDADYSORTYZQPWGMBLNAQOFODSNXSZFURUNPMZGHTAJUJROIGMRKIZHSFUSKIZJJTLGOEEPBMIXISDHOAIFNFEKKSLEXSJLSGLCYYFEQBKIZZTQQXBQZAPXAAIFQEIXELQEZGFEPCKFPGXULLAHXTSRXDEMKFKABUTAABSLNQBNMXNEPODPGAORYJXCHCGKECLJVRBPRLHORREEIZOBSHDSCETTTNFTSMQPQIJBLKNZDMXOTRBNMTKHHCZQQMSLOAXJQKRHDGZVGITHYGVDXRTVBJEAHYBYRYKJAVXPOKHFFMEPHAGFOOPFNKQAUGYLVPWUJUPCUGGIXGRAMELUTEPYILBIUOCKKUUBJROQFTXMZRLXBAMHSDTEKRRIKZUFNLGTQAEUINMBPYTWXULQNIIRXHHGQDPENXAJNWXULFBNKBRINUMTRBFWBYVNKNKDFR';
var needle = 'ABCDA'; // the order of letters doesn't matter

var letters = {};
needle.split('').forEach(function(ch) {
  letters[ch] = letters[ch] || 0;
  letters[ch]++;
});

var shortestSubstringLength = haystack.length;
var shortestSubstrings = []; // storage for found substrings

var startingPos = 0;
var length;
var currentPos;
var notFound;
var letterKeys = Object.keys(letters); // unique leters
do {
  lettersLeft = JSON.parse(JSON.stringify(letters)); // copy letters count object
  notFound = false;
  posStart = haystack.length;
  posEnd = 0;
  letterKeys.forEach(function(ch) {
    currentPos = startingPos;
    while (!notFound && lettersLeft[ch] > 0) {
      currentPos = haystack.indexOf(ch, currentPos);
      if (currentPos >= 0) {
        lettersLeft[ch]--;
        posStart = Math.min(currentPos, posStart);
        posEnd = Math.max(currentPos, posEnd);
        currentPos++;
      } else {
        notFound = true;
      }
    }
  });
  if (!notFound) {
    length = posEnd - posStart + 1;
    startingPos = posStart + 1; // starting position for next iteration
  }
  if (!notFound && length === shortestSubstringLength) {
    shortestSubstrings.push(haystack.substr(posStart, length));
  }
  if (!notFound && length < shortestSubstringLength) {
    shortestSubstrings = [haystack.substr(posStart, length)];
    shortestSubstringLength = length;
  }
} while (!notFound);

console.log(shortestSubstrings);
1
也许没有使用正则表达式那么清晰（对我来说，正则表达式从来不是很清晰:D），但您可以使用一种“蛮力”方法（并不是那么蛮力）。创建一个字符串的“有效”点索引（即带有所需字母的点），并在其上使用双重循环迭代，获取包含至少5个这些点的子字符串，检查它们是否是有效解决方案。这可能不是最有效的方法，但易于实现、理解和优化。 

var haystack="UGDVWUDDPRQLUZMSZOJPSIKAIHLTONYXAULECXXKWFQOIKELWOHRVRUCXIAASKHMWTMAJEWGEESLWRTQKVHRRCDYXNTLDSUPXMQTQDFAQAPYBGXPOLOCLFQNGNKPKOBHZWHRXAWAWJKMTJSLDLNHMUGVVOPSAMRUJEYUOBPFNEHPZZCLPNZKWMTCXERPZRFKSXVEZTYCXFRHRGEITWHRRYPWSVAYBUHCERJXDCYAVICPTNBGIODLYLMEYLISEYNXNMCDPJJRCTLYNFMJZQNCLAGHUDVLYIGASGXSZYPZKLAWQUDVNTWGFFYFFSMQWUNUPZRJMTHACFELGHDZEJWFDWVPYOZEVEJKQWHQAHOCIYWGVLPSHFESCGEUCJGYLGDWPIWIDWZZXRUFXERABQJOXZALQOCSAYBRHXQQGUDADYSORTYZQPWGMBLNAQOFODSNXSZFURUNPMZGHTAJUJROIGMRKIZHSFUSKIZJJTLGOEEPBMIXISDHOAIFNFEKKSLEXSJLSGLCYYFEQBKIZZTQQXBQZAPXAAIFQEIXELQEZGFEPCKFPGXULLAHXTSRXDEMKFKABUTAABSLNQBNMXNEPODPGAORYJXCHCGKECLJVRBPRLHORREEIZOBSHDSCETTTNFTSMQPQIJBLKNZDMXOTRBNMTKHHCZQQMSLOAXJQKRHDGZVGITHYGVDXRTVBJEAHYBYRYKJAVXPOKHFFMEPHAGFOOPFNKQAUGYLVPWUJUPCUGGIXGR";
var needle="ABCD";
var size=haystack.length;
var candidate_substring="";
var minimal_length=size;
var solutions=new Array();
var points=Array();
for(var i=0;i<size;i++){
 if(needle.indexOf(haystack[i])>-1) points.push(i);
}
var limit_i= points.length-4;
var limit_k= points.length;
for (var i=0;i<limit_i;i++){
  for(var k=i;k<limit_k;k++){
 if(points[k]-points[i]+1<=minimal_length){
  candidate_substring=haystack.substr(points[i],points[k]-points[i]+1);
  if(is_valid(candidate_substring)){
    solutions.push(candidate_substring);
    if(candidate_substring.length < minimal_length) minimal_length=candidate_substring.length;
  }
 }
  }
}
document.write('<p>Solution length:'+minimal_length+'<p>');
for(var i=0;i<solutions.length;i++){
  if(solutions[i].length<=minimal_length) document.write('<p>Solution:'+solutions[i]+'<p>');
}

function is_valid(candidate_substring){
  //verify we've got all characters
  for(var j=0;j<candidate_substring.length;j++){
    if(candidate_substring.indexOf(needle.charAt(j))<0) return false;
  }
  //...and verify we have two "A"
  if(candidate_substring.indexOf("A")==candidate_substring.lastIndexOf("A")) return false;
  return true;
}

0

我在一次面试中遇到了这个编码任务，我想出了另一个解决方案（虽然不如上面的那个优化，但可能更容易理解）。

function MinWindowSubstring(strArr) { 

  const N = strArr[0];
  const K = strArr[1];

  const letters = {};

  K.split('').forEach( (character) => {
    letters[character] = letters[character] ? letters[character] + 1 : 1;
  });

  let possibleSequencesList = [];
  
  const letterKeys = Object.keys(letters);

  for(let i=0; i< N.length; i++) {

    const char = N[i];

    if (new String(letterKeys).indexOf(char) !== -1) {
    
      // found a character in the string 

      // update all previus sequences
      possibleSequencesList.forEach((seq) => {
        if(!seq.sequenceComplete) {
          seq[char] = seq[char]-1;
          seq.lastIndex = i;

          // check if sequence is complete
          var sequenceComplete = true;
          letterKeys.forEach( (letter) => {
            if(seq[letter] > 0) {
              sequenceComplete = false;
            }
          });

          seq.sequenceComplete = sequenceComplete
        }
      })

      // create a new sequence starting from it 
      const newSeq = {
        startPoint: i,
        lastIndex: i,
        sequenceComplete: false,
        ...letters
      }

      newSeq[char] = newSeq[char]-1;

      possibleSequencesList.push(newSeq);
    }
  }

  // cleanup sequences 
  let sequencesList = possibleSequencesList.filter(sequence => sequence.sequenceComplete);
  
  let output = [];

  let minLength = N.length;
  // find the smalles one
  sequencesList.forEach( seq => {
      if( (seq.lastIndex - seq.startPoint) < minLength) {
        minLength = seq.lastIndex - seq.startPoint;
        output = N.substring(seq.startPoint, seq.lastIndex + 1);
      }
  })
   
  return output; 
}
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接