代码之家 › 专栏 › 技术社区 › user944513

如何在两个字符串中获取公共子字符串以保持顺序?

html javascript

-1

user944513 · 技术社区 · 8 年前

我想解决一个问题 hackerrank 但我不能解决那个问题

有人能帮我完成错误的逻辑实现吗?

问题

打印最长字符串的长度,使其同时是s1和s2的子字符串。

样本输入

HARRY
SALLY

样品输出

解释

从Harry和Sally中删除零个或多个字符可以形成的最长字符串是Ay,其长度为2。

样本输入1

AA
BB

样本输出1

解释1

aa和bb没有共同的字符,因此输出为0

样本输入2

SHINCHAN
NOHARAAA

样本输出2

解释2

在维持秩序的同时,新昌和野原之间可以形成的最长的字符串是nha。

我写了一些逻辑,如下:

 

   function commonChild(s1, s2) {

    var arr = s2.split(),
        currenString = '',
        maxLength = 0,
        index = -1;
  console.log(arr);

    for (var i = 0; i < s1.length; i++) {
        var char = s1.charAt(i),
            charIndex = arr.indexOf(char);
        console.log(char)
        if (index < charIndex) {
            index = charIndex;
            currenString +=char;
        }

        maxLength= Math.max(maxLength,currenString.length)
    }

    return maxLength;

}


commonChild('ABCDEF', 'FBDAMN');


console.log(commonChild('ABCDEF', 'FBDAMN'));

4 回复 | 直到 8 年前

-1

Programmer 8 年前

基于您的代码进行编辑。一个小小的改变就是改变 var arr = s2.split() 到 split('') . 逻辑中的主要变化是,我添加了一个循环,每次从另一个字符(第一个循环从第一个循环,第二个循环从第二个循环,等等)遍历字符串。

function commonChild(s1, s2) {
  var arr = s2.split(''),
    currenString = '',
    maxLength = 0,
    index = -1,
    j = -1;
  for (var ii = 0; ii < s1.length; ii++) {
    index = -1;
    currenString = '';
    for (var i = ii; i < s1.length; i++) {
      var char = s1.charAt(i),
        j = arr.indexOf(char);
      if (index < j) {
        index = j;
        currenString += char;
      }
      maxLength = Math.max(maxLength, currenString.length)
    }
  }
  return maxLength;
}
console.log(commonChild('ABCDEF', 'FBDAMN'));

TessavWalstijn solid90 8 年前

对不起。这是一个未经优化的解决方案。

function maxCommon(a, b, offset) {
  offset = offset || 0;

  if (a === b) {
    return [[a, b]];
  }
  var possibleSolns = [];
  for (var i = 0 + offset; i < a.length; i++) {
    for (var j = 0 + offset; j < b.length; j++) {
      if (a.charAt(i) === b.charAt(j)) {
        possibleSolns.push([
          a.substring(0, offset) + a.substring(i),
          b.substring(0, offset) +b.substring(j)
        ]);
        break;
      }
    }
  }

  var results = [];
  possibleSolns.forEach(function(soln) {
    var s = maxCommon(soln[0], soln[1], offset+1);
    if (s.length === 0) {
      s = [[soln[0].substring(0, offset +1), soln[1].substring(0, offset +1)]];
    }
    results = results.concat(s);
  });
  return results;
}

var maxLen = -1;
var soln = null;
maxCommon("ABCDEF", "FBDAMN").map(function(_) {
  return _[0];
}).forEach(function(_) {
  if (_.length > maxLen) {
    soln = _;
    maxLen = _.length;
  }
});

console.log(soln);

achini 8 年前

使用火山灰和扩散操作,你可以这样做。

const test = (first, second) => {
  const stringArray1 = [...first];
  const stringArray2 = [...second];
  return _.intersection(stringArray1, stringArray2).length;
}

console.log(test('ABCDEF', 'FBDAMN'));

-1

TessavWalstijn solid90 8 年前

我在回答中保留了你的大部分逻辑:

function commonChild(s1, s2) {
  var // Sets strings to arrays
    arrayString1 = s1.split(""),
    arrayString2 = s2.split(""),
    collectedChars = "",
    maxLength = 0,
    max = arrayString1.length;
  

  for (var i = 0; i < max; i++) {
    var
      char = arrayString1[i],
      count = arrayString2.indexOf(char);
     
    // check if char is in second string and not in collected
    if (count != -1 && collectedChars.indexOf(char) == -1) {
      collectedChars += char;
      maxLength++;
    }
  }

  return maxLength;
}

// expected output 4
console.log(commonChild(
                'ABCDEF',
                'FBDAMN'
            ));

// expected output 1
console.log(commonChild(
                'AA',
                'FBDAMN'
            ));