1 Reverse String
Write a function that reverses a string. The input string is given as an array of characters s
.
You must do this by modifying the input array in-place with O(1)
extra memory.
Example 1:
Input: s = ["h","e","l","l","o"] Output: ["o","l","l","e","h"]
Example 2:
Input: s = ["H","a","n","n","a","h"] Output: ["h","a","n","n","a","H"]
Constraints:
1 <= s.length <= 105
s[i]
is a printable ascii character.
Solution:
/**
* @param {character[]} s
* @return {void} Do not return anything, modify s in-place instead.
*/
var reverseString = function(s) {
let start = 0;
let end = s.length - 1;
while (start < end) {
let temp = s[start];
s[start] = s[end];
s[end] = temp;
start++;
end--;
}
};
2 Longest Common Prefix
Write a function to find the longest common prefix string amongst an array of strings.
If there is no common prefix, return an empty string ""
.
Example 1:
Input: strs = ["flower","flow","flight"] Output: "fl"
Example 2:
Input: strs = ["dog","racecar","car"] Output: "" Explanation: There is no common prefix among the input strings.
Constraints:
1 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i]
consists of only lowercase English letters.
Solution:
/**
* @param {string[]} strs
* @return {string}
*/
var longestCommonPrefix = function(strs) {
let prefix = strs[0];
for(let i=1; i<strs.length;i++) {
while(strs[i].indexOf(prefix) != 0) {
prefix = prefix.substring(0, prefix.length -1);
if(!prefix) {
return "";
}
}
}
return prefix;
};
3 Reverse Words in a String
Given an input string s
, reverse the order of the words.
A word is defined as a sequence of non-space characters. The words in s
will be separated by at least one space.
Return a string of the words in reverse order concatenated by a single space.
Note that s
may contain leading or trailing spaces or multiple spaces between two words. The returned string should only have a single space separating the words. Do not include any extra spaces.
Example 1:
Input: s = "the sky is blue" Output: "blue is sky the"
Example 2:
Input: s = " hello world " Output: "world hello" Explanation: Your reversed string should not contain leading or trailing spaces.
Example 3:
Input: s = "a good example" Output: "example good a" Explanation: You need to reduce multiple spaces between two words to a single space in the reversed string.
Constraints:
1 <= s.length <= 104
s
contains English letters (upper-case and lower-case), digits, and spaces' '
.- There is at least one word in
s
.
Follow-up: If the string data type is mutable in your language, can you solve it in-place with O(1)
extra space?
Solution:
/**
* @param {string} str
* @return {string}
*/
var reverseWords = function(str) {
let last = str.length -1;
let output = '';
while(last >= 0) {
if(str.charAt(last) == ' ') {
last--;
} else {
let chartStart = last;
while(last >= 0 && str.charAt(last) != ' ') {
last--;
}
if(output.length > 0) {
output = output + ' ';
}
for(let k=last+1;k<=chartStart;k++) {
output += str[k];
}
}
}
return output;
};
4 Longest Palindromic Substring
Given a string s
, return the longest
palindromic
substring in s
.
Example 1:
Input: s = "babad" Output: "bab" Explanation: "aba" is also a valid answer.
Example 2:
Input: s = "cbbd" Output: "bb"
Constraints:
1 <= s.length <= 1000
s
consist of only digits and English letters.
Solution:
/**
* @param {string} s
* @return {string}
*/
var longestPalindrome = function(s) {
if(s == null || s.length < 1) {
return '';
}
let start = 0;
let end = 0;
for(let i=0;i<s.length;i++) {
let len1 = checkPalindrom(s, i, i);
let len2 = checkPalindrom(s,i, i+1);
let len = Math.max(len1, len2);
if(len > end - start) {
start = i - (len -1)/2
end = i + (len/2);
}
}
return s.substring(start, end+1);
};
function checkPalindrom(s, left, right){
while(left >= 0 && right < s.length && s[left] == s[right]) {
left--;
right++;
}
return right - left - 1;
};
5 Longest Substring Without Repeating Characters
Given a string s
, find the length of the longest
substring without repeating characters.
Example 1:
Input: s = "abcabcbb" Output: 3 Explanation: The answer is "abc", with the length of 3.
Example 2:
Input: s = "bbbbb" Output: 1 Explanation: The answer is "b", with the length of 1.
Example 3:
Input: s = "pwwkew" Output: 3 Explanation: The answer is "wke", with the length of 3. Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.
Constraints:
0 <= s.length <= 5 * 104
s
consists of English letters, digits, symbols and spaces.
Solution:
/**
* @param {string} s
* @return {number}
*/
var lengthOfLongestSubstring = function(s) {
let maincount = 0;
let count = 0;
for(let i=0;i<s.length;i++) {
count = checkUnique(s, i);
if(maincount < count) {
maincount = count;
}
}
return maincount;
};
function checkUnique(s, t) {
let map = {};
let count = 0;
for(let i=t;i<s.length;i++) {
if(map[s[i]]) {
return count;
} else {
map[s[i]] = 1;
count++;
}
}
return count;
}
6 Valid Parentheses
Given a string s
containing just the characters '('
, ')'
, '{'
, '}'
, '['
and ']'
, determine if the input string is valid.
An input string is valid if:
- Open brackets must be closed by the same type of brackets.
- Open brackets must be closed in the correct order.
- Every close bracket has a corresponding open bracket of the same type.
Example 1:
Input: s = "()" Output: true
Example 2:
Input: s = "()[]{}" Output: true
Example 3:
Input: s = "(]" Output: false
Constraints:
1 <= s.length <= 104
s
consists of parentheses only'()[]{}'
.
Solution:
/**
* @param {string} s
* @return {boolean}
*/
var isValid = function(s) {
let matcharray = {
"(": ")",
"{": "}",
"[": "]"
};
let stack1 = [];
for(let i=0;i<s.length;i++) {
if(matcharray[s[i]]) {
stack1.push(matcharray[s[i]]);
} else if(stack1[stack1.length -1] == s[i]) {
stack1.pop();
} else {
return false;
}
}
return stack1.length > 0 ? false : true;
};
7 Decode String
Given an encoded string, return its decoded string.
The encoding rule is: k[encoded_string]
, where the encoded_string
inside the square brackets is being repeated exactly k
times. Note that k
is guaranteed to be a positive integer.
You may assume that the input string is always valid; there are no extra white spaces, square brackets are well-formed, etc. Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k
. For example, there will not be input like 3a
or 2[4]
.
The test cases are generated so that the length of the output will never exceed 105
.
Example 1:
Input: s = "3[a]2[bc]" Output: "aaabcbc"
Example 2:
Input: s = "3[a2[c]]" Output: "accaccacc"
Example 3:
Input: s = "2[abc]3[cd]ef" Output: "abcabccdcdcdef"
Constraints:
1 <= s.length <= 30
s
consists of lowercase English letters, digits, and square brackets'[]'
.s
is guaranteed to be a valid input.- All the integers in
s
are in the range[1, 300]
.
Solution:
/**
* @param {string} s
* @return {string}
*/
var decodeString = function(s) {
let output = '';
let numstack = [];
let strstack = [];
let count = 0;
for(let i = 0; i < s.length; i++) {
if(!isNaN(s[i])) {
let num = s[i];
while((i+1) < s.length && !isNaN(s[i+1])) {
num = num*10 + s[i+1];
i++;
}
numstack.push(num);
} else if(s[i] == '[') {
strstack.push(output);
output = '';
} else if (s[i] == ']') {
let repeat = numstack.pop();
let temp = strstack.pop();
for(j=0;j<repeat;++j) {
temp = temp + output;
}
output = temp;
} else {
output = output + s[i];
}
}
return output;
};
8 Valid Anagram
Given two strings s
and t
, return true
if t
is an anagram of s
, and false
otherwise.
An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.
Example 1:
Input: s = "anagram", t = "nagaram" Output: true
Example 2:
Input: s = "rat", t = "car" Output: false
Constraints:
1 <= s.length, t.length <= 5 * 104
s
andt
consist of lowercase English letters.
Follow up: What if the inputs contain Unicode characters? How would you adapt your solution to such a case?
/**
* @param {string} s
* @param {string} t
* @return {boolean}
*/
var isAnagram = function(s, t) {
let newList = {};
if(s.length != t.length) {
return false;
}
for(let i=0;i<s.length;i++) {
if(newList[s[i]]) {
newList[s[i]]++;
} else {
newList[s[i]] = 1;
}
}
for(let i=0;i<t.length;i++) {
if(newList[t[i]]) {
newList[t[i]]--;
} else {
return false;
}
}
return true;
};
9 Repeated DNA Sequences
The DNA sequence is composed of a series of nucleotides abbreviated as 'A'
, 'C'
, 'G'
, and 'T'
.
- For example,
"ACGAATTCCG"
is a DNA sequence.
When studying DNA, it is useful to identify repeated sequences within the DNA.
Given a string s
that represents a DNA sequence, return all the 10
-letter-long sequences (substrings) that occur more than once in a DNA molecule. You may return the answer in any order.
Example 1:
Input: s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT" Output: ["AAAAACCCCC","CCCCCAAAAA"]
Example 2:
Input: s = "AAAAAAAAAAAAA" Output: ["AAAAAAAAAA"]
Constraints:
1 <= s.length <= 105
s[i]
is either'A'
,'C'
,'G'
, or'T'
.
Solution:
/**
* @param {string} s
* @return {string[]}
*/
var findRepeatedDnaSequences = function(s) {
let newMap = {};
// enter all entry in map
for(let i=0; i<=s.length -10;i++) {
let subStr = s.substring(i,i+10);
if(newMap[subStr]) {
newMap[subStr]++;
} else {
newMap[subStr] = 1;
}
}
let output = [];
for(let index in newMap) {
if(newMap.hasOwnProperty(index)) {
if(newMap[index] > 1) {
output.push(index);
}
}
}
return output;
};