let longestCommonPrefix = function(strs) {
if (!strs.length) return '';
let index = 0, curr = '';
for (;;)
{
for (let i = 0; i < strs.length; i++) {
if (strs[i].length <= index) {
return strs[0].substring(0, index); //?
}
if (curr === '') curr = strs[i][index];
if (curr !== strs[i][index]) {
return strs[0].substring(0, index);
}
if (i === strs.length - 1) {
curr = '';
index++
}
}
}
return '';
};
Category: String
let isPalindrome = function(s) {
let start = 0, end = s.length - 1, regex = /\w/i;
while (start < end) {
if (!s[start].match(regex)) {
start++;
}
else if (!s[end].match(regex)) {
end--;
}
else {
if (s[start].toLowerCase() !== s[end].toLowerCase()) return false;
start++;
end--;
}
}
return true;
}
let romanToInt = function(s) {
if (!s) return 0;
let mapping = {
'I': 1,
'V': 5,
'X': 10,
'L': 50,
'C': 100,
'D': 500,
'M': 1000
}
let result = 0;
for (let i = s.length - 1; i >= 0;) {
if (mapping[s[i]] > mapping[s[i - 1]]) {
result += mapping[s[i]] - mapping[s[i - 1]];
i -= 2;
}
else {
result += mapping[s[i]];
i -= 1;
}
}
return result;
}
let reorganizeString = function(S) {
let chars = {}, max = 0;
for(let i = 0; i < S.length;i++) {
if (chars[S[i]]) {
chars[S[i]] = chars[S[i]] + 1;
max = Math.max(chars[S[i]], max);
}
else {
chars[S[i]] = 1;
}
}
console.log(max, Math.floor((S.length + 1) / 2));
if (max > (S.length + 1) / 2) {
return "";
}
let result = [], index = 0;
const keys = Object.keys(chars).sort((a, b) => chars[b] - chars[a]); //?
while (keys.length) { //?
const key = keys.shift(); //?
result[index] = key;
if (chars[key] - 1 > 0) {
chars[key] = chars[key] - 1;
keys.unshift(key); //?
}
index += 2; //?
if (index >= S.length) {
index = 1;
}
}
return result.join('');
};
let topKFrequent = function(words, k) {
let map = new Map();
words.forEach(word => {
if(map.has(word)) {
map.set(word, map.get(word) + 1);
}
else {
map.set(word, 1);
}
});
return [...map].sort((x, y) => {
const f1 = x[1], f2 = y[1]
if (f1 < f2) return 1;
if (f1 > f2) return -1;
return x[0].localeCompare(y[0]);
}).map(x => x[0]).slice(0, k);
};
let mostCommonWord = function(paragraph, banned) {
let wordMap = paragraph.toLowerCase()
.replace(/\W+/g, ' ')
.trim()
.split(' ')
.filter(word => banned.indexOf(word) < 0)
.reduce((map, y) => {
if (map.has(y)) {
map.set(y, map.get(y) + 1);
}
else {
map.set(y, 1);
}
return map;
}, new Map()); //?
let word = null, count = 0;
for (let [key, val] of wordMap) {
if (val > count) {
count = val;
word = key;
}
}
return word;
};
let reorderLogFiles = function(logs) {
let alpha = [],
numbers = [];
const isNumber = (str) => {
const [, content] = str.split(' ');
return content.match(/\d+/);
}
const getBody = (str) => {
return str.substring(str.indexOf(' ') + 1);
}
// separate alpha from numbers
logs.forEach(log => {
if (isNumber(log)) {
numbers.push(log);
}
else {
alpha.push(log);
}
});
let comparator = (x, y) => {
let compareResult = getBody(x).localeCompare(getBody(y));
if (compareResult === 0) {
return x.localeCompare(y);
}
return compareResult;
}
return [...alpha.sort(comparator), ...numbers];
};
Categories
Decode String
let decodeString = function(str) {
if (str.indexOf("[") < 0) {
return str;
}
let openingIndex = [];
let newStr = "";
for (let i = 0; i < str.length; i++) {
if (str[i] === "[") {
openingIndex.push(i);
newStr += str[i];
}
else if (str[i] === "]") {
let opening = openingIndex.pop();
let allMultipliers = str.substring(0, opening).match(/\d+/g);
let multiplier = allMultipliers[allMultipliers.length - 1];
let data = str.substring(opening + 1, i);
if (data.indexOf("[") < 0) {
newStr = newStr.substring(0, newStr.lastIndexOf("[") - multiplier.length) + data.repeat(multiplier);
console.log({opening, multiplier, data, newStr});
}
else {
newStr += str[i];
}
}
else {
newStr += str[i];
}
}
return decodeString(newStr);
};
let intToRoman = function(num) {
const mapping = {
1000: 'M',
900: 'CM',
500: 'D',
400: 'CD',
100: 'C',
90: 'XC',
50: 'L',
40: 'XL',
10: 'X',
9: 'IX',
5: 'V',
4: 'IV',
1: 'I'
}
let result = "";
for(let divisor of [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1]) {
if (num >= divisor) {
let quotient = Math.floor(num / divisor);
result = result + mapping[divisor].repeat(quotient);
num = num % divisor;
}
}
return result;
}
let lookAndSay = function(nth, number = "1") {
if (nth === 1) return number;
let index = 0,
counter = 1,
currentNumber = "";
let result = "";
while (index < number.length) {
if (index === 0) {
currentNumber = number[index];
}
else if (currentNumber === number[index]) {
counter++;
}
else if (currentNumber !== number[index]) {
result = `${result}${counter}${currentNumber}`;//?
counter = 1;
currentNumber = number[index];
}
index++;
}
result = `${result}${counter}${currentNumber}`;//?
return lookAndSay(--nth, result);
}