jirengu / frontend-interview

前端笔试面试题题库
1.29k stars 139 forks source link

JS 字符串操作面试题 #1

Open jirengu opened 7 years ago

jirengu commented 7 years ago

请用JavaScript 实现一个方法,该方法能够判断两个字符串是否匹配, 如:

function isMatch(str1, str2) {
  // ...
}
isMatch('something', 'ginhtemos')  // true
isMatch('aaa', 'aa')  //false
isMatch('abb', 'baa')  //false
isMatch('hello', 'olelh')  //true

题目来源——饥人谷大前端群前端爱好者 尐

pingfengafei commented 7 years ago

抱歉,盲人coding。

function isMatch(str1, str2){
   return str1.split('').sort().join('') === str2.split('').sort().join('');
}

-----------分割线---------------

这里,不应该叫相等,本质是判断一个字符串是否是回文。js有经典方法:

function isMatch(str1, str2){
  return str1 === str2.split('').reverse().join('');
}

wait, 好像在哪里看到过,js的内置方法效率不高,比如,splice就特别低。来个改进算法,直接比较字符串:

function isMatch1() {
  var str1 = arguments[0];
  var str2 = arguments[1];
  var len1 = str1.length, len2 = str2.length;

  if (len1 !== len2) {
    return false;
  } else {
    for (var i = 0, j = len2 - 1; i < len1; i++, j--) {
      if (str1[i] !== str2[j]) {
        return false;
      }
    }
    return true;
  }
}

顺便写个比较函数:

var str1 = '1234567890';
var str2 = '0987654321';

function test() {
  console.time('isMath');
  for (var i = 0; i < 10000; i++) {
    isMatch(str1, str2);
  }
  console.timeEnd('isMath');

  console.time('isMath1');
  for (var i = 0; i < 10000; i++) {
    isMatch1(str1, str2);
  }
  console.timeEnd('isMath1');
}

test()

运行时间:

isMath: 20.526ms
isMath1: 1.306ms
Jemair commented 7 years ago
function foo(str1, str2) {
  return !str1.split('').sort().join('').replace(str2.split('').sort().join(''), '');
}
LZ0211 commented 7 years ago
function isMatch(str1, str2) {
  var len1 = str1.length,len2=str2.length;
  if (len1 !== len2)return false;
  for (var i=0;i<len1 ; i++){
      if (str1[i] !== str2[len1-i-1]){
          return false;
      }
  }
  return true;
}
QilongLiao commented 7 years ago

function isMatch(str1,str2){ return str1.split('').sort().join('')==str2.split('').sort().join(''); }

xcatliu commented 7 years ago

@pingfengafei @LZ0211 没看清题目吧,并不是判断是否为回文,而是只要 str1 的字符串能够通过重新排列成为 str2 即可。

@Jemair @QilongLiao 没问题,不过时间复杂度是 O(n^2),还有优化的空间。

我也给个代码吧:

function isMatch(str1, str2) {
  if (typeof str1 !== 'string' || typeof str2 !== 'string') return false;
  if (str1 === '' && str2 === '') return true;
  if (str1.length !== str2.length) return false;

  var strCollection1 = getCollection(str1);
  var strCollection2 = getCollection(str2);

  return collectionsAreEqual(strCollection1, strCollection2);
}

/**
 * Return the collection of numbers of each letter in str
 * Example input: "hello"
 * Example output:
 * {
 *   “h“: 1,
 *   "e": 1,
 *   "l": 2,
 *   "o": 1
 * }
 */
function getCollection(str) {
}

/**
 * Return true if collections are equal, otherwise false
 */
function collectionsAreEqual(collection1, collection2) {
}

后面两个函数比较简单,就不实现了。

ahonn commented 7 years ago

@xcatliu 实现了你所说的另外两个函数。 if (str1 === '' && str2 === '') return true; 可以直接 if (str1 === str2) return true; 相同的字符串就直接不用比了。

function isMatch(str1, str2) {
    if (typeof str1 !== 'string' || typeof str2 !== 'string') return false;
    if (str1 === str2) return true;
    if (str1.length !== str2.length) return false;

    var str1Collection = getCollection(str1),
        str2Collection = getCollection(str2);

    return collectionAreEqual(str1Collection, str2Collection);
}

function getCollection(str) {
    var collection = {};
    for (var i = 0, len = str.length; i < len; ++i) {
        if (collection[str[i]] === undefined) {
            collection[str[i]] = 0
        } else {
            collection[str[i]]++;
        }
    }
    return collection;
}

function collectionAreEqual(collection1, collection2) {
    var keys1 = Object.keys(collection1),
          keys2 = Object.keys(collection2);

    if (keys1.length !== keys2.length) return false;
    for (var key in collection1) {
        if (collection1[key] !== collection2[key]) {
            return false;
        }
    }
    return true;
}
QilongLiao commented 7 years ago

@xcatliu 你没看懂代码吧,题目不就是判断两个字符包含的字符一样吗? 我的代码有什么问题,题目上的测试都能通过啊。

xcatliu commented 7 years ago

@QilongLiao 抱歉,的确是我看错了。你的代码没问题。 不过你的时间复杂度是 O(N logN),还有优化的空间。

xcatliu commented 7 years ago

@ahonn

if (collection[str[i]] == null) {

这个地方应该判断 undefined 而不是 null 吧?

QilongLiao commented 7 years ago

@xcatliu 应该是O( nLog n) 吧,默认sort一般应该都是用的快速排序算法

ahonn commented 7 years ago

@xcatliu 的确应该是 === undefined

xcatliu commented 7 years ago

@QilongLiao 根据这个回答,确实是 O(N logN) 不过会根据数组类型选择 quicksort, mergesort 或 selection sort

ningt commented 7 years ago

O(N) 方法,遍历两个string各一遍

function isMatch(str1, str2) {
  if (typeof str1 !== 'string' || typeof str2 !== 'string') return false;
  if (str1 === str2) return true;
  if (str1.length !== str2.length) return false;

  const count_map = {}; // 记录每个字符出现次数

  for (let i = 0; i < str1.length; i++) {
    if (str1[i] in count_map)
      count_map[str1[i]]++;
    else
      count_map[str1[i]] = 1;
  }

  for (let i = 0; i < str2.length; i++) {
    if (!(str2[i] in count_map) ||
      --count_map[str2[i]] < 0
    )
      return false;
  }
  return true;
}

console.log(isMatch('something', 'ginhtemos'));
console.log(isMatch('aaa', 'aa'));
console.log(isMatch('abb', 'baa'));
console.log(isMatch('hello', 'olelh'));
oceanpad commented 7 years ago

@xcatliu 虽说你的代码时间复杂度比较优化,但是消耗的时间却比 @pingfengafei 的第二个算法多啊。右图为证,有什么错误请指点。这个大致是因为你的单个函数时间复杂度比较低,但是是因为三个函数一起求结果,导致整时间消耗比较大。 screen shot 2017-01-03 at 12 32 29

xcatliu commented 7 years ago

@oceanpad 确实如果只是很短的字符串匹配的话,三个函数调用会很浪费资源,有可能比 O(N logN) 更慢。 还有一个可能的原因是,对于你给出的例子,1234567890 是基本已排好序的,调用 sort() 就不是 O(N logN) 而是 O(N) 了。

建议多做一些测试用例,包含不同字符串长度(比如 length = 100, 1000, 10000, 100000 ...)的,顺序打乱的。

oceanpad commented 7 years ago

@xcatliu 好的。非常感谢回复,我再做一下测试。请问有什么js讨论群或者社区什么的嘛?求推荐加入啊!

xcatliu commented 7 years ago

@oceanpad 我个人觉得学习技术的过程中,qq 微信群之类的效果并不好,一是知识传播效率低,二是难以积累。 我推荐多看别人经过多年工作经验积累的书籍,博客或者代码。那里面都是精华。 算法题的话,我自己积累了个仓库: https://github.com/xcatliu/leetcode

社区的话我会逛逛 v2ex 和 cnode。

oceanpad commented 7 years ago

@xcatliu 恩,very good, 非常感谢。我会试着去做这些。

kylewh commented 7 years ago

/* leetcode里回文定义不比较非字母&数字以外的字符

特殊情况: &&&aba&& -> true corner case: 空字符串 -> true 无字母&数字 -> true */

function isPalindrome(s){ if(s == '' || s.length == 0 ) { //空字符串默认为真。 return true; }

let head = 0, tail = s.length-1;

while (head < tail){
    while(head < s.length && !isValid(s[head]) ){ //如果当前字符不是字母或者阿拉伯字母,头索引向后跳
        head++;
    }
    if(head == s.length ){  // 如果字符串里没有任何字母和阿拉伯字母,默认为真。
        return true;
    }
    while( tail >=0 && !isValid(s[tail])) { //如果当前字符不是字母或者阿拉伯字母,尾索引向前跳
        tail--;
    }
    if(s[head].toLowerCase() !== s[tail].toLowerCase() ){ //如果头尾索引对应字符不相等,跳出循环,不是回文。
        break;
    }else { //头尾向彼此各移动一位
        head++; 
        tail--;
    }
}
return tail <= head;

function isValid (c){ //判断是否为字母或者数字
    return (c.charCodeAt(0)>=65 && c.charCodeAt(0)<= 90) || (c.charCodeAt(0)>=97 && c.charCodeAt(0)<= 122) || (c.charCodeAt(0)>=48 && c.charCodeAt(0)<= 57);
}

}

isPalindrome('');//true isPalindrome('&^%$#@^*(');//true isPalindrome('abcdcba'); // true isPalindrome('&&&aba&&'); //true isPalindrome('abcdefg'); //false

facejiong commented 7 years ago

O(N),使用哈希

function isMatched(str1, str2){
  if(str1.length !== str2.length){
    return false
  }
  var hash = {}
  var returnValue = true
  str1.split('').map((n)=>{
    hash[n] = hash[n] === undefined ? 1 : hash[n] + 1
  })
  console.log(hash)
  str2.split('').map((n)=>{
    if(hash[n]) {
      hash[n]--
    }
  })
 console.log(hash)
 Object.keys(hash).map((n) => {
   if (hash[n] !== 0) {
     returnValue=false
   }
  })
  return returnValue
}
hwwgh555 commented 7 years ago

@pingfengafei 第一个方法很简洁;但是第二个方法isMatch1()有问题,可以测试下isMatch("yyyzx","zxyyy"),返回false

Chersquwn commented 7 years ago

@hwwgh555 他把这题当作回文处理了,但是这题是乱序,不是回文

nsxz945 commented 7 years ago

//遍历str1,在str2中消去相应字符

function isMatch(str1,str2){
    if (str1.length !== str2.length) {return false}
    for(key in str1){
        str2 = str2.replace(str1[key]+'','')
    }
    if (str2.length === 0) {
        return true}else return false
}
leecz commented 7 years ago
let string1 = (Math.random() * 1e64).toString(36)
let string2 = string1 + 'test'
let string3 = 'test' + string1
let string4 = 'aaaa' + string1

function isMatch1 (str1, str2) {
  if (str1 === str2) return true
  if (str1.length !== str2.length) return false
  for (let key in str1) {
    str2 = str2.replace(str1[key], '')
  }
  if (str2.length === 0) {
    return true
  }
  return false
}

function isMatch (str1, str2) {
  if (str1 === str2) return true
  if (str1.length !== str2.length) return false

  let hash1 = getHash(str1)
  let hash2 = getHash(str2)

  if (hash1.length !== hash2.length) return false
  for (let key in hash1) {
    if (hash1[key] !== hash2[key]) return false
  }
  return true
}

function getHash (str) {
  let hash = {}
  for (let i = 0, k = str.length; i < k; i++) {
    hash[ str[i] ] ? hash[ str[i] ]++ : hash[ str[i] ] = 1
  }
  return hash
}

function isMatch2 (str1, str2) {
  return str1.split('').sort().join('') === str2.split('').sort().join('')
}

console.time('isMatch')
for (let i = 0; i < 10000; i++) {
  isMatch(string2, string3)
  isMatch(string3, string4)
}
console.timeEnd('isMatch')

console.time('isMatch1')
for (let i = 0; i < 10000; i++) {
  isMatch1(string2, string3)
  isMatch1(string3, string4)
}
console.timeEnd('isMatch1')

console.time('isMatch2')
for (let i = 0; i < 10000; i++) {
  isMatch2(string2, string3)
  isMatch2(string3, string4)
}
console.timeEnd('isMatch2')

isMatch: 422.634ms isMatch1: 422.838ms isMatch2: 243.686ms

实验结果: js 内置方法最快

ningt commented 7 years ago

@leecz isMatch & isMatch1 都是O(N^2), isMatch2是O(Nlog(N))

在我的电脑上试了下之前我写的O(N)的isMatch3和你的isMatch2

isMatch2: 365.8681640625ms isMatch3: 283.929931640625ms

function isMatch3(str1, str2) {
  if (typeof str1 !== 'string' || typeof str2 !== 'string') return false;
  if (str1 === str2) return true;
  if (str1.length !== str2.length) return false;

  const count_map = {}; // 记录每个字符出现次数

  for (let i = 0; i < str1.length; i++) {
    if (str1[i] in count_map)
      count_map[str1[i]]++;
    else
      count_map[str1[i]] = 1;
  }

  for (let i = 0; i < str2.length; i++) {
    if (!(str2[i] in count_map) ||
      --count_map[str2[i]] < 0
    )
      return false;
  }
  return true;
}
leecz commented 7 years ago

@ningt

我试了下, isMatch3 是你的,还是比 isMatch2 慢一点,可能是测试数据引起的差异吧

isMatch: 486.409ms
isMatch1: 438.228ms
isMatch2: 242.219ms
isMatch3: 349.418ms
➜  
isMatch: 337.261ms
isMatch1: 399.418ms
isMatch2: 212.109ms
isMatch3: 251.071ms
➜ 
isMatch: 370.396ms
isMatch1: 408.410ms
isMatch2: 244.797ms
isMatch3: 253.958ms
➜  
isMatch: 420.306ms
isMatch1: 394.388ms
isMatch2: 225.221ms
isMatch3: 313.595ms
ningt commented 7 years ago

@leecz 我用的跟你一样的数据,估计是电脑的差异吧

leecz commented 7 years ago

@ningt 好吧,也有可能是 node 版本的问题, 我 跑了很多次, isMatch3 更快的只有1次。

leecz commented 7 years ago

@ningt 在浏览器中 isMatch3 更快

ningt commented 7 years ago

@leecz 哦 对,我用的chrome测试的。看来node对sort有做特殊的优化

bpup commented 7 years ago
function isMatch(str1, str2) {
  var str1arr=[...str1].sort()
  var str2arr=[...str2].sort()
  return str1arr.every((ele,i)=>{
      return str2arr[i]==ele
  })
}
liyuanqiu commented 5 years ago
function isMatch(str1, str2) {
  var len1 = str1.length,len2=str2.length;
  if (len1 !== len2)return false;
  for (var i=0;i<len1 ; i++){
      if (str1[i] !== str2[len1-i-1]){
          return false;
      }
  }
  return true;
}

耳边回响着原谅我这一生不羁放荡爱自由...(代码格式)

lxx0904 commented 5 years ago

function stringBJ(str1, str2){ return str1 === str2.split("").reverse().join(""); }

chaooo commented 5 years ago

function isMatch(str1, str2) { return (String(str1).split('').sort().join('') === String(str2).split('').sort().join('')); }