В нашей серии вопросов для собеседования по JS сегодня мы обсудим 10 строковых задач на собеседовании.

Проблема 1: Действительная анаграмма

Анаграмма — это слово или фраза, образованная путем перестановки букв другого слова или фразы, обычно с использованием всех исходных букв ровно один раз.

Example 1:
Input: s = "anagram", t = "nagaram"
Output: true

Example 2:
Input: s = "rat", t = "car"
Output: false

Решения 1:

const validAnagram = (s, t) => {
  if(s.length !== t.length) return false;
  if(s.split('').sort().join('') === t.split('').sort().join('')) return true;
  return false;
}

Решение 2:

const validAnagram = (s, t) => {
  let obj = {};
  for(let i = 0; i < s.length; i++) {
   if(obj.hasOwnProperty(s[i])) obj[s[i]] +=1;
   else obj[s[i]] = 1;
   }
  for(let j= 0; j< t.length; j++) {
   if(obj.hasOwnProperty(t[j])) obj[t[j]] -=1;
   else return false;
   if(obj[t[j]] === 0 ) delete obj[t[j]];
  }
  return Object.keys(obj).length === 0
}

Проблема 2: Групповые анаграммы

Получив массив строк strs, сгруппируйте анаграммы вместе. Вы можете вернуть ответ в любом порядке.

Анаграмма – это слово или фраза, образованная путем перестановки букв другого слова или фразы, обычно с использованием всех исходных букв ровно один раз.

Example 1:
Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]

Example 2:
Input: strs = [""]
Output: [[""]]

Example 3:
Input: strs = ["a"]
Output: [["a"]]

Решение:

const groupAnagram = s => {
    let obj = {};
    for(let i = 0; i < s.length; i++) {
        let a = s[i].split('').sort().join('');
        if(obj.hasOwnProperty(a)) {
            obj[a].push(s[i]);
        } else{
            obj[a] = [s[i]]
        }
    }
    return Object.values(obj);
}

Проблема 3: Действительные скобки

Учитывая строку s, содержащую только символы '(', ')', '{', '}', '[' и ']', определите, допустима ли входная строка.

Входная строка действительна, если:

  1. Открытые скобки должны быть закрыты однотипными скобками.
  2. Открытые скобки должны быть закрыты в правильном порядке.
  3. Каждой закрывающей скобке соответствует открытая скобка того же типа.
Example 1:
Input: s = "()"
Output: true

Example 2:
Input: s = "()[]{}"
Output: true

Example 3:
Input: s = "(]"
Output: false

Решение:

const validParentheses = s => {
  let obj = {
    '{':'}',
    '[':']',
    '(':')',
  }
  let stack = [];
  for(let i = 0 ; i < s.length; i++){
    if(stack[stack.length - 1] === s[i]) stack.pop();
    else stack.push(obj[s[i]])
  }
  return stack.length === 0

}

Задача 4: Действительный палиндром

Фраза является палиндромом, если после преобразования всех прописных букв в строчные и удаления всех неалфавитно-цифровых символов она читается одинаково вперед и назад. Буквенно-цифровые символы включают буквы и цифры.

Получив строку s, вернуть true, если это палиндром, илиfalseв противном случае.

Example 1:
Input: s = "A man, a plan, a canal: Panama"
Output: true
Explanation: "amanaplanacanalpanama" is a palindrome.

Example 2:
Input: s = "race a car"
Output: false
Explanation: "raceacar" is not a palindrome.

Решение:

const validPalindrome = s = >{
  let str  = s.replaceAll(/[^A-Za-z0-9]+/ig, "").toLowerCase();
  return str === str.split('').reverse().join('')
}

Проблема 5: Кодировать и декодировать строки

Разработайте алгоритм для кодирования списка строк в строку. Затем кодированная строка отправляется по сети и декодируется обратно в исходный список строк.

Input: ["lint", "code"]
Output: ["lint", "code"]

Решение

const encode = s => {
  let out = "";
  for(let i = 0; i < s.length; i++){
     out +=s[i].length+ '$'+s[i]
  }
return out;
}

const decode = s => {
  let result = [];
  let left = 0; 
  while(left < s.length-1) {
    if( s[left+1] === '$'){
        result.push(s.substr(left+2, s[left]));
        left += Number(s[left])+2;
    }
  }
return result
}

Проблема 6: Палиндромные подстроки

Получив строку s, вернуть количество подстрок-палиндромов в ней.

Строка является палиндромом, если она читается так же, как в прямом, так и в обратном направлении.

Подстрока – это непрерывная последовательность символов в строке.

Example 1:
Input: s = "abc"
Output: 3
Explanation: Three palindromic strings: "a", "b", "c".

Example 2:
Input: s = "aaa"
Output: 6
Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".

Решение:

var countSubstrings = function(s) {
    let res = 0;
    for (let i = 0 ; i < s.length; i++) {
        res += checkPalindrom(s, i, i)
        res += checkPalindrom(s, i, i+1)
    }
    return res
};

const checkPalindrom = (s, left, right) => {
    let res = 0;
    while(left>= 0 && right <= s.length && s[left] === s[right]) {
        res += 1;
        left -= 1;
        right += 1;
    }
    return res
}

Проблема 7: Самая длинная палиндромная подстрока

Получив строку s, вернуть самую длинную палиндромную подстроку в s.

Example 1:
Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.

Example 2:
Input: s = "cbbd"
Output: "bb"

Решение:

const longestPalindromicSubstr = s => {
    let res = '';
    let reslen = 0;
     for(var i = 0 ; i < s.length; i++) {
         //for odd palindrome
         let left = i; 
         let right = i;
         while(left >= 0 && right < s.length && s[left] === s[right]) {
            if(right - left +1 > reslen) {
                res= s.substring(left, right+1);
                reslen  = right-left +1;
            } 
            left -= 1;
            right += 1;
         }
        //for even palindrome
         let left2 = i; 
         let right2 = i+1;
         while(left2 >= 0 && right2 < s.length && s[left2] === s[right2]) {
            if(right2 - left2 +1 > reslen) {
                res = s.substring(left2, right2+1);
                reslen  = right2 - left2 +1;
            }
            left2 -= 1;
            right2 += 1;
         }
     }
     return res
}