В нашей серии вопросов для собеседования по 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
, содержащую только символы '('
, ')'
, '{'
, '}'
, '['
и ']'
, определите, допустима ли входная строка.
Входная строка действительна, если:
- Открытые скобки должны быть закрыты однотипными скобками.
- Открытые скобки должны быть закрыты в правильном порядке.
- Каждой закрывающей скобке соответствует открытая скобка того же типа.
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 }