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 '';
};
Month: May 2020
let generate = function(numRows) {
if (numRows === 0) return [];
let result = [];
for (let i = 1; i <= numRows;i++) {
let row = [];
for (let j = 0; j < i; j++) {
if (j === 0 || j === i - 1) {
row[j] = 1;
}
else {
row[j] = result[i - 2][j - 1] + result[i - 2][j];
}
}
result.push(row);
}
return result;
};
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 uniquePathsWithObstacles = function(obstacleGrid) {
if (!obstacleGrid || !obstacleGrid.length) return 0;
function markNextRowsAsZero(col) {
for (let i = col; i < maxCol; i++) {
obstacleGrid[0][i] = 0;
}
}
function markNextColumnsAsZero(row) {
for (let i = row; i < maxRow; i++) {
obstacleGrid[i][0] = 0;
}
}
let maxRow = obstacleGrid.length,
maxCol = obstacleGrid[0].length,
OBSTACLE = 1, VISITED = -1;
// first block is obstacle return 0;
if (obstacleGrid[0][0] === OBSTACLE) {
return 0;
}
// mark all first rows as either 1 or zero
for (let col = 0; col < maxCol;col++) {
if (obstacleGrid[0][col] === OBSTACLE) {
markNextRowsAsZero(col);
break;
}
else {
obstacleGrid[0][col] = 1;
}
}
// mark all first columns as either 1 or zero
for (let row = 1; row < maxRow;row++) {
if (obstacleGrid[row][0] === OBSTACLE) {
markNextColumnsAsZero(row);
break;
}
else {
obstacleGrid[row][0] = 1;
}
}
for (let row = 1; row < maxRow;row++) {
for (let col = 1; col < maxCol;col++) {
if (obstacleGrid[row][col] === OBSTACLE) {
obstacleGrid[row][col] = 0;
}
else {
obstacleGrid[row][col] =
obstacleGrid[row - 1][col] +
obstacleGrid[row][col - 1];
}
}
}
return obstacleGrid[maxRow - 1][maxCol - 1];
};
Categories
Unique Paths (Iterative)
let uniquePaths = function(m, n) {
let getKey = (row, col) => `${row}${col}`;
let cache = { }
for (let row = 1; row <= m; row++) {
for (let col = 1; col <= n; col++) {
if (row === 1) {
cache[getKey(row, col)] = 1;
}
else if (col === 1) {
cache[getKey(row, col)] = 1;
}
else {
cache[getKey(row, col)] = cache[getKey(row-1, col)] + cache[getKey(row, col - 1)];
}
}
}
return cache[getKey(m,n)];
};
let uniquePaths = function(m, n) {
let results = new Set();
function getPath(row, col, path = '') {
if (row >= m && col >= n) {
results.add(path);
return;
}
if (row === m) {
// go right if at the bottom row
getPath(row, col + 1, path + 'R');
}
else if (col === n) {
// go down if at the end column
getPath(row + 1, col, path + 'D');
}
else {
// go down and go right
getPath(row, col + 1, path + 'R');
getPath(row + 1, col, path + 'D');
}
}
getPath(1, 1, 'S');
return results.size;
};
let minPathSum = function(grid) {
if(!grid || !grid.length) return 0;
let maxRow = grid.length, maxCol = grid[0].length;
for (let row = 0; row < maxRow;row++) {
for (let col = 0; col < maxCol;col++) {
console.log(row, col);
if (row === 0) {
grid[row][col] = grid[row][col] + (grid[row][col - 1] || 0);
}
else if (col === 0) {
grid[row][col] = grid[row][col] + grid[row - 1][col];
} else {
grid[row][col] = Math.min(
grid[row][col] + grid[row - 1][col], // top
grid[row][col] + grid[row][col - 1] // left
);
}
}
}
return grid[maxRow - 1][maxCol - 1];
};
let minPathSum = function(grid) {
if(!grid || !grid.length) return 0;
let maxRow = grid.length, maxCol = grid[0].length;
function sum(row, col, total, path = '') {
const val = grid[row][col] + total; //?
if (row === maxRow - 1 && col === maxCol - 1) {
return val;
} //?
if (row === maxRow - 1) {
return sum(row, col + 1, val);
}
else if (col === maxCol - 1) {
return sum(row + 1, col, val);
} else {
const down = sum(row + 1, col, val);
const right = sum(row, col + 1, val);
return Math.min(down, right);
}
}
return sum(0, 0, 0);
};
Categories
Path Sum II
let pathSum = function(root, sum, results = [], result = []) {
if (!root) return results;
if (sum - root.val === 0 && !root.left && !root.right) {
results.push([...result, root.val]);
}
pathSum(root.left, sum - root.val, results, [...result, root.val]);
pathSum(root.right, sum - root.val, results, [...result, root.val]);
return results;
};