Devops Engineer

This Solution use 2D DP. beat 90% solutions, very simple.

Here are some conditions to figure out, then the logic can be very straightforward.

1, If p.charAt(j) == s.charAt(i) : dp[i][j] = dp[i-1][j-1];
2, If p.charAt(j) == '.' : dp[i][j] = dp[i-1][j-1];
3, If p.charAt(j) == '*': 
here are two sub conditions:
1 if p.charAt(j-1) != s.charAt(i) : dp[i][j] = dp[i][j-2] //in this case, a* only counts as empty
2 if p.charAt(i-1) == s.charAt(i) or p.charAt(i-1) == '.':
dp[i][j] = dp[i-1][j] //in this case, a* counts as multiple a 
or dp[i][j] = dp[i][j-1] // in this case, a* counts as single a
or dp[i][j] = dp[i][j-2] // in this case, a* counts as empty
Here is the solution

public boolean isMatch(String s, String p) {

if (s == null || p == null) {
return false;
}
boolean[][] dp = new boolean[s.length()+1][p.length()+1];
dp[0][0] = true;
for (int i = 0; i < p.length(); i++) {
if (p.charAt(i) == '*' && dp[0][i-1]) {
dp[0][i+1] = true;
}
}
for (int i = 0 ; i < s.length(); i++) {
for (int j = 0; j < p.length(); j++) {
if (p.charAt(j) == '.') {
dp[i+1][j+1] = dp[i][j];
}
if (p.charAt(j) == s.charAt(i)) {
dp[i+1][j+1] = dp[i][j];
}
if (p.charAt(j) == '*') {
if (p.charAt(j-1) != s.charAt(i) && p.charAt(j-1) != '.') {
dp[i+1][j+1] = dp[i+1][j-1];
} else {
dp[i+1][j+1] = (dp[i+1][j] || dp[i][j+1] || dp[i+1][j-1]);
}
}
}
}
return dp[s.length()][p.length()];
}

class Solution {
public:
//for storing already solved problems
unordered_map mp;


bool isScramble(string s1, string s2) {
//base cases

int n = s1.size();

//if both string are not equal in size
if(s2.size()!=n)
return false;

//if both string are equal
if(s1==s2)
return true; 



//if code is reached to this condition then following this are sure:
//1. size of both string is equal
//2. string are not equal
//so size is equal (where size==1) and they are not equal then obviously false
//example 'a' and 'b' size is equal ,string are not equal
if(n==1)
return false;

string key = s1+" "+s2;

//check if this problem has already been solved
if(mp.find(key)!=mp.end())
return mp[key];

//for every iteration it can two condition 
//1.we should proceed without swapping
//2.we should swap before looking next
for(int i=1;i {

//ex of without swap: gr|eat and rg|eat
bool withoutswap = (
//left part of first and second string
isScramble(s1.substr(0,i),s2.substr(0,i)) 

&&

//right part of first and second string;
isScramble(s1.substr(i),s2.substr(i))
);



//if without swap give us right answer then we do not need 
//to call the recursion withswap
if(withoutswap)
return true;

//ex of withswap: gr|eat rge|at
//here we compare "gr" with "at" and "eat" with "rge"
bool withswap = (
//left part of first and right part of second 
isScramble(s1.substr(0,i),s2.substr(n-i)) 

&&

//right part of first and left part of second
isScramble(s1.substr(i),s2.substr(0,n-i)) 
);



//if withswap give us right answer then we return true
//otherwise the for loop do it work
if(withswap)
return true;
//we are not returning false in else case 
//because we want to check further cases with the for loop
}


return mp[key] = false;

}
};

class Solution {
public String longestPalindrome(String s) {
//Approach : treat each character as mid of the palindromic string and check if its left and right character are same or not if they are same then decrement left and increment right and after checking it for each charater determine maximum length which is maximum length of palindromic string 
// To get palindromic substring return substring from start to start + maximum length
int n = s.length();
if(n <= 1) return s;
int maxLen = 1;
int start = 0;
//for odd length 
for(int i=0;i= 0 && r < n && s.charAt(l) == s.charAt(r)){
l--;
r++;
}
int len = r-l-1;
if(len > maxLen){
maxLen = len;
start = l+1;
}
}
//for Even length 
for(int i=0;i= 0 && r maxLen){
maxLen = len;
start = l+1;
}
}
return s.substring(start,start+maxLen);
}
}

Intuition
Approach
Only used two loops and for removeing dublicate triplets used simple javaScript objects.

Complexity
Time complexity:
Space complexity:
Code
/**
* @param {number[]} nums
* @return {number[][]}
*/
var threeSum = function(nums) {

let obj={}
nums=nums.sort((a,b)=>a-b)
// console.log(nums)
for(let start=0;start0){
right--
}else if(nums[left]+nums[right]+nums[start]<0){
left++
}
}
}
return (Object.values(obj))
};

class Solution {
public:
double myPow(double x, int n) {
if(n==0) return 1;
if(n<0){
n = abs(n);
x = 1/x;
}
if(n%2==0) return myPow(x*x,n/2);
else return x*myPow(x,n-1);
}
};

Intuition : Since we are asked to calculate all the possible combinations, hence we have to use backtracking

Concept : In every backtracking problem, there are two things to keep in mind, which we will explore here as well :

Base Case : Every problem of backtracking has some base case that tells us at which point we have to stop with the recursion process. In our case, when the size of our array current equals to k i.e. current.size()=k, we stop with the recursion and add it to our final result ans.

Conditions : There is just one thing to keep in mind here:
After generating combinations corresponding to a particular number i, proceed to the next element by popping the element from the temporary array current, as we used that already.

We basically consider a number i, generate the combinations corresponding to it by recursively calling it again, and then we pop that element as we are done with it and proceed to the next!!

And thats it!! We are done!!