常见字符串算法

[Leo-lin214]

对字符串数据结构常见的算法进行总结，也为了更好滴应对后面深入学习算法。

表示数值的字符串

请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。

例如：字符串‘+100’、‘5e2’都表示数值，但是12e、1a3.14、1e+4.3就不是数值。

答案

  const isNumber = str => {
    if (!str) return false;
    let hasPoint = false;
    let hasExp = false;
    for (let i = 0; i < str.length; i++) {
      const temp = str[i];
      if (temp <= 9 && temp >= 0) {
        continue;
      } else if (temp === 'e' || temp === 'E') {
        if (hasExp || i === 0 || i === str.length - 1) return false;
        hasExp = true;
        continue;
      } else if (temp === '.') {
        if (hasExp || hasPoint || i === 0 || i === str.length - 1) return false;
        hasPoint = true;
        continue;
      } else if (temp === '-' || temp === '+') {
        if (i !== 0 || str[i - 1] !== 'e' || str[i - 1] !== 'E') return false;
        continue;
      } else {
        return false;
      }
    }
    return true;
  }
  

考虑所有情况。

• 只能出现数字、符号位（+或-）、小数点、指数位（e或E）。
• 小数点，指数符号只能出现一次、且不能出现在开头结尾。
• 指数位出现后，指数位后面不允许出现小数点。
• 符号位只能出现在开头和指数位后面。

正则表达式匹配

请实现一个函数用来匹配包括.和*的表达式。

其中.表示任意一个字符，而*表示它前面的字符可以出现任意次（包括0次）。

答案

  const isMatch = (str, pattern) => {
    if (!str || !pattern) return false;
    return handleMatch(str, 0, pattern, 0);
  }
  const handleMatch = (str, sIndex, pattern, pIndex) => {
    if (sIndex === str.length && pIndex === pattern.length) return true;
    if (sIndex !== str.length && pIndex === pattern.length) return false;
    if (pIndex < pattern.length - 1 && pattern[pIndex + 1] === '*') {
      if (sIndex < str.length && (str[sIndex] === pattern[pIndex] || pattern[pIndex] === '.')) {
        return handleMatch(str, sIndex, pattern, pIndex + 2) ||
          handleMatch(str, sIndex + 1, pattern, pIndex + 2) ||
          handleMatch(str, sIndex + 1, pattern, pIndex);
      } else {
        return handleMatch(str, sIndex, pattern, pIndex + 2);
      }
    }
    if (sIndex < str.length && (str[sIndex] === pattern[pIndex] || pattern[pIndex] === '.')) {
      return handleMatch(str, sIndex + 1, pattern, pIndex + 1);
    }
    return false;
  } 
  

字符串的全排列

输入一个字符串，按字典序打印出该字符串中字符的所有排列。

例如输入字符串abc，则其全排列的所有字符串为：abc，acb，bac，bca，cab，cba。

答案

  const logPermutation = str => {
    const result = [];
    if (str) {
      const queue = str.split('');
      handlePermutation(queue, result);
    }
    return result;
  }
  const handlePermutation = (queue, result, temp = '', current = '') => {
    current += temp;
    if (queue.length === 0) {
      result.push(current);
      return;
    }
    for (let i = 0; i < queue.length; i++) {
      const temp = queue.shift();
      handlePermutation(queue, result, temp, current);
      queue.push(temp);
    }
  }