Software Developer

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 has two conditions 
//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 with swap
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 with swap 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 character 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 removing duplicate 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))
};