Amit Bansal
BAN USER
Javascript Implementation -
function match(str, pattern){
let BACKSLASH = false;
let CAPSLOCK = false;
let stack = [];
str.split('').forEach((char, index) => {
if(char === "\\"){
BACKSLASH = !BACKSLASH;
}else{
if(BACKSLASH && char === 'b'){
stack.pop();
BACKSLASH = !BACKSLASH;
}
else if(BACKSLASH && char === 'c'){
CAPSLOCK = !CAPSLOCK;
BACKSLASH = !BACKSLASH;
}
else{
stack.push(CAPSLOCK ? char.toUpperCase() : char);
}
}
});
return stack.join('') === pattern;
}
console.log(match("abc\\b", "ab"));
console.log(match("abc\\ca", "abcA"));
console.log(match("abc\\bde\\cfd", "abdeFD"));
console.log(match("\\ba", "a"));
console.log(match("abc\\cde\\cfd", "abcDEfd"));
console.log(match("a\\ba", "a"));
console.log(match("a\\b\\cb", "B"));
console.log(match("a\\b", ""));
console.log(match("\\cz", "Z"));
console.log(match("Abc\\b\\bt", "At"));
console.log(match("\\caef\\b\\c\\bt", "At"));
Create a map for each element in the array. if all values are even for all keys in the map then yes array can be divided into 2 subarrays.
- Amit Bansal March 31, 2018/**
* Javascript Implementation.
* reverseStringInPlace
Write program for the following case
Reverse string (string is stored in an array)
Input:- "This is an example"
Output:-sihT si na elpmaxe
*/
function reverseStringInPlace(str) {
let words = str.split(' ');
for(let index = 0, length = words.length; index < length; index++) {
words[index] = words[index].split('').reverse().join('');
}
return words.join(' ');
}
let str = 'This is an example';
console.log("reverseStringInPlace ->");
console.log("Input : " + str);
console.log("Output : " + reverseStringInPlace(str));
/**
* Javascript Implementation.
* validateStringWithPattern
Given an input string and ordering string, need to return true if
the ordering string is present in Input string.
input = "hello world!"
ordering = "hlo!"
result = FALSE (all Ls are not before all Os)
input = "hello world!"
ordering = "!od"
result = FALSE (the input has '!' coming after 'o' and after 'd',
but the pattern needs it to come before 'o' and 'd')
input = "hello world!"
ordering = "he!"
result = TRUE
input = "aaaabbbcccc"
ordering = "ac"
result = TRUE
*/
function validateStringWithPattern(str, pattern) {
let map = {};
for(let index = 0, length = str.length; index < length; index++) {
const char = str[index];
if(map[char]) {
map[char].push(index);
} else {
map[char] = [index];
}
}
for(let index = 1, length = pattern.length; index < length; index++) {
let mapCharArr1 = map[pattern[index-1]];
let mapCharArr2 = map[pattern[index]];
//First index of second char should be more than the last index of first char.
if(mapCharArr2[0] < mapCharArr1[mapCharArr1.length - 1]){
return false;
}
}
return true;
}
//Test Case 1
let str = 'hello world!';
let pattern1 = 'hlo!';
let pattern2 = '!od';
let pattern3 = 'he!';
console.log("Validating String -> '"+ str + "' with Pattern -> '" +pattern1 + "' ===> " + validateStringWithPattern(str, pattern1));
console.log("Validating String -> '"+ str + "' with Pattern -> '" +pattern2 + "' ===> " + validateStringWithPattern(str, pattern2));
console.log("Validating String -> '"+ str + "' with Pattern -> '" +pattern3 + "' ===> " + validateStringWithPattern(str, pattern3));
//Test Case 2
str = 'aaaabbbcccc';
pattern1 = 'ac';
console.log("Validating String -> '"+ str + "' with Pattern -> '" +pattern1 + "' ===> " + validateStringWithPattern(str, pattern1));
/**
* Javascript Implementation.
* charByCount
You have a string aaabbdcccccf, transform it the following way => a3b2d1c5f1
ie: aabbaa -> a2b2a2 not a4b2
Input:
acaaabbbacdddd
aaabbdcccccf
aabbaa
Output:
a1c1a3b3a1c1d4
a3b2d1c5f1
a2b2a2
*/
function charByCount(str) {
let result = "";
let lastChar = str[0];
let counter = 0;
for(let index = 0, length = str.length; index < length; index++) {
const char = str[index];
if(char === lastChar) {
counter++;
} else {
result = result + lastChar + counter;
counter = 1; //reset the counter
lastChar = char; //reset the lastChar
}
// if str is ending with same last chars e.g. 'acaaabbbacdddd'
if(index === str.length - 1 && counter > 0) {
result = result + lastChar + counter;
}
}
console.log(result);
}
const str1 = 'acaaabbbacdddd'; // a1c1a3b3a1c1
const str2 = 'aaabbdcccccf'; // a3b2d1c5
const str3 = 'aabbaa'; // a2b2
console.log("charByCount -> "+str1);
charByCount(str1);
console.log("charByCount -> "+str2);
charByCount(str2);
console.log("charByCount -> "+str3);
charByCount(str3);
/**
* Javascript Implementation.
* uniqueCharByCount
Given a string, print out all of the unique characters
and the number of times it appeared in the string
Input:
geeksforgeek
acaaabbbacdddd
Output:
{ g: 2, e: 4, k: 2, s: 1, f: 1, o: 1, r: 1 }
{ a: 5, c: 2, b: 3, d: 4 }
*/
function uniqueCharByCount(str) {
let charByCountMap = {};
for(let index = 0, length = str.length; index < length; index++) {
const char = str[index];
if( !charByCountMap[char] ) {
charByCountMap[char] = 1;
} else {
charByCountMap[char] = charByCountMap[char] + 1;
}
}
console.log(charByCountMap);
}
const str = 'acaaabbbacdddd';
console.log("uniqueCharByCount -> "+str+" \n");
uniqueCharByCount(str);
/**
* Javascript Implementation.
* parenthesis-checker
Given an expression string exp, examine whether the pairs and the orders
of “{“,”}”,”(“,”)”,”[“,”]” are correct in exp.
For example, the program should print
'balanced' for exp = “[()]{}{[()()]()}” and
'not balanced' for exp = “[(])”
Input:
The first line of input contains an integer T denoting the number of test cases.
Each test case consists of a string of expression, in a separate line.
Output:
Print 'balanced' without quotes if the pair of parenthesis are balanced else print
'not balanced' in a separate line.
*/
function parenthesisChecker(str) {
let stack = [];
const openingParenthesis = ['{','(','['];
const closingParenthesis = ['}',')',']'];
let result = true;
for(let index = 0, length = str.length; index < length; index++) {
const char = str[index];
if(openingParenthesis.indexOf(char) > -1){
stack.push(char);
}
if(closingParenthesis.indexOf(char) > -1){
switch(stack.pop()){
case '{':
result = char === '}';
break;
case '(':
result = char === ')';
break;
case '[':
result = char === ']';
break;
}
// if result is false then immidiately return 'Non balanced'
if(!result) {
return "String is not balanced";
}
}
//console.log("Stack is = " + stack);
}
return 'String is balanced';
}
const str = '[()]{}{[()()]()}';
console.log("parenthesis-checker -> " + parenthesisChecker(str));
/**
* Javascript Implementation.
* Reverse the words in string eg -
* Input : 'The Sky is Blue '.
* output: 'Blue is Sky The'.
*/
function reverseWords(str) {
// Assumption: There is only one space between words.
return str.split(' ').reverse().join(' ');
}
const str = 'The Sky is Blue';
console.log("Before Reverse, String is -> " + str);
console.log("After Reverse String is -> " + reverseWords(str));
// Javascript Implementation -
/**
* Reverse this string 1+2*3-20. Note: 20 must be retained as is. Expected
* output: 20-3*2+1
*/
function reverseString(str) {
let startIndex = 0;
let stack = [];
for(let i = 0, length = str.length; i < length; i++) {
const char = str[i];
if(isNaN(char)){
let subStr = str.substring(startIndex, i);
stack.push(subStr);
stack.push(str[i]);
startIndex = i+1;
}
}
if(startIndex < str.length){
let subStr = str.substring(startIndex);
stack.push(subStr);
}
return stack.reverse().join('');
}
const str = "1+2*3-20+2000+";
console.log("Before Reverse String is -> " + str);
const reverseStr = reverseString(str);
console.log("After Reverse String is -> " + reverseStr);
Open Chat in New Window
The above implementation is without O(1) space.
Below implementation is with O(1) space
- Amit Bansal March 31, 2018