Top Google Questions

Looking to join Google? This problems list will give you a preliminary grasp of Google’s interview style and test sites, and conduct simulation exercises in advance. The list is updated based on how frequently problems appear in an interview.

CategoryDifficultyLikesDislikes
algorithmsHard (38.11%)263952897
Tags

Companies

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.

The overall run time complexity should be O(log (m+n)).

 

Example 1:

Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000
Explanation: merged array = [1,2,3] and median is 2.

Example 2:

Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.50000
Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.

 

Constraints:

  • nums1.length == m
  • nums2.length == n
  • 0 <= m <= 1000
  • 0 <= n <= 1000
  • 1 <= m + n <= 2000
  • -106 <= nums1[i], nums2[i] <= 106

Approach:

  • Create a new array with a size equal to the total number of elements in both input arrays.
  • Insert elements from both input arrays into the new array.
  • Sort the new array.
  • Find and return the median of the sorted array.

Time Complexity

  • In the worst case TC is O((n + m) * log(n + m)).

Space Complexity

  • O(n + m), where ‘n’ and ‘m’ are the sizes of the arrays.
				
					class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        // Get the sizes of both input arrays.
        int n = nums1.size();
        int m = nums2.size();

        // Merge the arrays into a single sorted array.
        vector<int> merged;
        for (int i = 0; i < n; i++) {
            merged.push_back(nums1[i]);
        }
        for (int i = 0; i < m; i++) {
            merged.push_back(nums2[i]);
        }

        // Sort the merged array.
        sort(merged.begin(), merged.end());

        // Calculate the total number of elements in the merged array.
        int total = merged.size();

        if (total % 2 == 1) {
            // If the total number of elements is odd, return the middle element as the median.
            return static_cast<double>(merged[total / 2]);
        } else {
            // If the total number of elements is even, calculate the average of the two middle elements as the median.
            int middle1 = merged[total / 2 - 1];
            int middle2 = merged[total / 2];
            return (static_cast<double>(middle1) + static_cast<double>(middle2)) / 2.0;
        }
    }
};
				
			
CategoryDifficultyLikesDislikes
algorithmsHard (27.86%)114651918
Tags

Companies

Given an input string s and a pattern p, implement regular expression matching with support for '.' and '*' where:

  • '.' Matches any single character.​​​​
  • '*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

 

Example 1:

Input: s = "aa", p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".

Example 2:

Input: s = "aa", p = "a*"
Output: true
Explanation: '*' means zero or more of the preceding element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".

Example 3:

Input: s = "ab", p = ".*"
Output: true
Explanation: ".*" means "zero or more (*) of any character (.)".

 

Constraints:

  • 1 <= s.length <= 20
  • 1 <= p.length <= 20
  • s contains only lowercase English letters.
  • p contains only lowercase English letters, '.', and '*'.
  • It is guaranteed for each appearance of the character '*', there will be a previous valid character to match.

Approach:

 

  • We can use dynamic programming to solve this problem. Let dp[i][j] be a boolean value representing whether the first i characters of s match the first j characters of p.

    First, we initialize dp[0][0] to true since an empty pattern matches an empty string.

    Next, we need to consider the first row of the dp matrix. If the pattern p starts with a ‘‘ then it can match zero occurrences, so we set dp[0][j] to dp[0][j-2] for all j where p[j-1] == ‘‘.

    Now we fill in the remaining cells of the dp matrix using the following rules:

    1. If the i-1th character of s matches the j-1th character of p or the j-1th character of p is ‘.’, then dp[i][j] is equal to dp[i-1][j-1].
    2. If the j-1th character of p is ‘*’, then we have two cases:
      a) Zero occurrences: dp[i][j] is equal to dp[i][j-2]
      b) One or more occurrences: dp[i][j] is equal to dp[i-1][j] if the i-1th character of s matches the j-2th character of p or the j-2th character of p is ‘.’.

    Finally, we return dp[m][n], which represents whether the entire string s matches the entire pattern p.

    Complexity:

    • Time Complexity:
      The time complexity of the algorithm is O(m * n), where m and n are the lengths of s and p, respectively. This is because we need to fill in the entire dp matrix.

    • Space Complexity:
      The space complexity of the algorithm is also O(m * n) because we need to create a dp matrix of size (m+1) x (n+1).

				
					class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.size(), n = p.size();
        std::vector<std::vector<bool>> dp(m+1, std::vector<bool>(n+1, false));
        dp[0][0] = true; // empty pattern matches empty string

        // initialize first row (empty string)
        for (int j = 1; j <= n; j++) {
            if (p[j-1] == '*')
                dp[0][j] = dp[0][j-2];
        }

        // fill in remaining cells
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (s[i-1] == p[j-1] || p[j-1] == '.') {
                    dp[i][j] = dp[i-1][j-1];
                } else if (p[j-1] == '*') {
                    dp[i][j] = dp[i][j-2]; // zero occurrences
                    if (s[i-1] == p[j-2] || p[j-2] == '.') {
                        dp[i][j] = dp[i][j] || dp[i-1][j]; // one or more occurrences
                    }
                }
            }
        }
        return dp[m][n];
    }
};
				
			
CategoryDifficultyLikesDislikes
algorithmsMedium (58.72%)17309903
Tags

Companies

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.

A mapping of digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

 

Example 1:

Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

Example 2:

Input: digits = ""
Output: []

Example 3:

Input: digits = "2"
Output: ["a","b","c"]

 

Constraints:

  • 0 <= digits.length <= 4
  • digits[i] is a digit in the range ['2', '9'].

Approach:

Intuition

  • The logic is so simple, all you need to do is to create map similar to the phone map.
  • and apply multiple neasted loops, and just keep tacking characters in sequence.
  • so in case of 23, we will do the following loop
        for (char c : mp[2])
            for (char d : mp[3])
                ans.push_back(c+d);
     
  • And keeping in mind that if we have any 1 we should neglect them
  • ie: 213 should give the same answer as 23

Approach

  • Firstly define a static phone map
  • Secondly remove all ones from the digits using this built it method:
        digits.erase(remove(digits.begin(), digits.end(), '1'), digits.end()); // remove 1s from string 
     
  • now all we need to do is to apply the neasted loops as you can see in intuition, so to do so I used recursive method backtracking

Backtracking (i, digits, s, ans)

return type and parameters

  1. Return Type: it returns nothing
  2. Parameter:
    • i: the index of the current digit.
    • digits: the given string of digits.
    • s: this is the formatted string till the current call.
    • ans: this is the vector in which we store all possible combinations.

Basecase

  • our basecase is when i is same as the length of the given digits, because all the result strings must be same length as the given digits.
  • so if it happens, we should make sure that our string has at least one character, because in test case 2, he insert empty string, so we should return empty vector not {”}.
  • if this happend just insert s in the result.
  • then return.

recursive logic

  • just loop over all characters exist in the map of the current digit, and increment i by 1 in each call and append that character to s
        for (auto chr : mp[digits[i]])
            backtracking(i + 1, digits, s + chr, ans)
     

Complexity

  • Time complexity:
  1. O(4^l) where l is the length of the given digits string

4 not 3 because 7 & 9 contains 4 charachters, so there may be a case where we have 9999 or 7777 so it will be 4^4.

  • Space complexity:
  1. O(4 * 4^l) = O(4 ^ (l + 1)) which is the matrix for storing all possible combinations.
				
					class Solution {
    public:
    #define DPSolver ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    map<char, vector<char>> mp = {
        {'2', {'a', 'b', 'c'}},
        {'3', {'d', 'e', 'f'}},
        {'4', {'g', 'h', 'i'}},
        {'5', {'j', 'k', 'l'}},
        {'6', {'m', 'n', 'o'}},
        {'7', {'p', 'q', 'r', 's'}},
        {'8', {'t', 'u', 'v'}},
        {'9', {'w', 'x', 'y', 'z'}}};

    void backtracking(int i, string digits, string s, vector<string> &ans)
    {
        // base cases
        if (i == digits.length())
        {
            if (s.length())
                ans.push_back(s);
            return;
        }

        for (auto chr : mp[digits[i]])
            backtracking(i + 1, digits, s + chr, ans);
    }

    vector<string> letterCombinations(string digits)
    {
        DPSolver;
        // remove all ones
        digits.erase(remove(digits.begin(), digits.end(), '1'), digits.end());
        vector<string> ans;
        backtracking(0, digits, "", ans);
        return ans;
    }

};
				
			
CategoryDifficultyLikesDislikes
algorithmsEasy (40.19%)222791501
Tags

Companies

Given a string s containing just the characters '('')''{''}''[' and ']', determine if the input string is valid.

An input string is valid if:

  1. Open brackets must be closed by the same type of brackets.
  2. Open brackets must be closed in the correct order.
  3. 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 '()[]{}'.

Approach:

Intuition

The problem requires us to determine if the given string of brackets is valid or not. We can use a stack data structure to keep track of opening brackets encountered and check if they match with the corresponding closing brackets.

Approach

Here is the step-by-step approach of the algorithm:

  1. Initialize an empty stack.

  2. Traverse the input string character by character.

  3. If the current character is an opening bracket (i.e., ‘(‘, ‘{‘, ‘[‘), push it onto the stack.

  4. If the current character is a closing bracket (i.e., ‘)’, ‘}’, ‘]’), check if the stack is empty. If it is empty, return false, because the closing bracket does not have a corresponding opening bracket. Otherwise, pop the top element from the stack and check if it matches the current closing bracket. If it does not match, return false, because the brackets are not valid.

  5. After traversing the entire input string, if the stack is empty, return true, because all opening brackets have been matched with their corresponding closing brackets. Otherwise, return false, because some opening brackets have not been matched with their corresponding closing brackets.

Complexity

  • Time complexity:

The time complexity of the solution is O(n)O(n), where n is the length of the input string. This is because we traverse the string once and perform constant time operations for each character.

  • Space complexity:

The space complexity of the solution is O(n)O(n), where n is the length of the input string. This is because the worst-case scenario is when all opening brackets are present in the string and the stack will have to store them all.

				
					class Solution {
public:
    bool isValid(string s) {
        stack<char> st; // create an empty stack to store opening brackets
        for (char c : s) { // loop through each character in the string
            if (c == '(' || c == '{' || c == '[') { // if the character is an opening bracket
                st.push(c); // push it onto the stack
            } else { // if the character is a closing bracket
                if (st.empty() || // if the stack is empty or 
                    (c == ')' && st.top() != '(') || // the closing bracket doesn't match the corresponding opening bracket at the top of the stack
                    (c == '}' && st.top() != '{') ||
                    (c == ']' && st.top() != '[')) {
                    return false; // the string is not valid, so return false
                }
                st.pop(); // otherwise, pop the opening bracket from the stack
            }
        }
        return st.empty(); // if the stack is empty, all opening brackets have been matched with their corresponding closing brackets,
                           // so the string is valid, otherwise, there are unmatched opening brackets, so return false
    }
};
				
			
CategoryDifficultyLikesDislikes
algorithmsMedium (73.49%)19774808
Tags

Companies

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

 

Example 1:

Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]

Example 2:

Input: n = 1
Output: ["()"]

 

Constraints:

  • 1 <= n <= 8

Approach:

Intuition

This problem is one of the classical recursion problems.
For any given n, lets say n = 2, we have to fill four places in our output (“_ _ _ _”). And each of these places can be either filled by an open braces “(” or a closed braces “)”.

Approach

                                "_  _  _  _"
                                / \     
                              '(' ')'
 

For every place we have two choices and 1 decision to make.
Our choices are to either use ‘(‘ or ‘)’.

Now lets try to visualize the recursive tree based upon the choices discussed above.

Initially, we have:
For n = 3
current ouput = “”
availableOpenBracketsCnt = 3 and availableCloseBracketsCnt = 3

The first choise is very simple. Since we can not start a balanced parenthesis sequence with ‘)’, we have only one choice in the begining. So our output will be ‘(‘ and count of open brackets left = 2 and count of closed brackets left = 3.

                                    op      ip
                                    ""   O-3, C-3
                            
                                    "(",O-2,C-3
                    
                "((",O-1,C-3                            "()", O-2,C-2

    "(((",0,3             "(()",1,2                       "()(",1,2

    "((()",0,2      "(()(",0,2    "(())",1,1        "()((",0,2      "()()",1,1

    "((())",0,1     "(()()",0,1   "(())(",0,1       "()(()",0,1     "()()(",0,1

    "((()))",0,0   "(()())",0,0   "(())()",0,0      "()(())",0,0    "()()()", 0,0
                        
 

Observation from the recursive tree

  • Whenever we have count of open brackets equal to the count of close brackets, we have only one choice – that is to use ‘(‘. Because, all the brackets till now have been balanced. And we can not start a new sequence with ‘)’.
  • Whenever, count of close bracket is 0, we can only use ‘(‘.
  • Whenever, count of open bracket is 0, we can only use ‘)’.
  • And for all the remaining cases, we have both the choices.
  • We get an answer, when count of open == 0 and count of close == 0.

Just convert these 5 observations into an algorithm and write the code.

 

				
					class Solution {
public:
    void solve(string op, int open, int close, vector<string> &ans){
        if(open == 0 && close == 0){
            ans.push_back(op);
            return;
        }
        //when count of open and close brackets are same then 
        //we have only one choice to put open bracket 
        if(open == close){
            string op1 = op;
            op1.push_back('(');
            solve(op1, open-1, close, ans);
        }
        else if(open == 0){
            //only choice is to put close brackets 
            string op1 = op;
            op1.push_back(')');
            solve(op1, open, close-1, ans);
        }
        else if(close == 0){
            //only choise is to use open bracket 
            string op1 = op;
            op1.push_back('(');
            solve(op1, open-1, close, ans);
        }
        else{
            string op1 = op;
            string op2 = op;
            op1.push_back('(');
            op2.push_back(')');
            solve(op1, open-1, close, ans);
            solve(op2, open, close-1, ans);
        }
    }
    vector<string> generateParenthesis(int n) {
        int open = n;
        int close = n;
        vector<string> ans;
        string op = "";
        solve(op, open, close, ans);
        return ans;
    }
};
				
			

You're Doing Great

Take a Break Man

CategoryDifficultyLikesDislikes
algorithmsHard (51.04%)18425658
Tags

Companies

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

Merge all the linked-lists into one sorted linked-list and return it.

 

Example 1:

Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked-lists are:
[
  1->4->5,
  1->3->4,
  2->6
]
merging them into one sorted list:
1->1->2->3->4->4->5->6

Example 2:

Input: lists = []
Output: []

Example 3:

Input: lists = [[]]
Output: []

 

Constraints:

  • k == lists.length
  • 0 <= k <= 104
  • 0 <= lists[i].length <= 500
  • -104 <= lists[i][j] <= 104
  • lists[i] is sorted in ascending order.
  • The sum of lists[i].length will not exceed 104.

Approach:

Intuition of this Problem:

This solution uses the merge sort algorithm to merge all the linked lists in the input vector into a single sorted linked list. The merge sort algorithm works by recursively dividing the input into halves, sorting each half separately, and then merging the two sorted halves into a single sorted output.

Approach for this Problem:

  1. Define a function merge that takes two pointers to linked lists as input and merges them in a sorted manner.

    • a. Create a dummy node with a value of -1 and a temporary node pointing to it.
    • b. Compare the first node of the left and right linked lists, and append the smaller one to the temporary node.
    • c. Continue this process until either of the lists becomes empty.
    • d. Append the remaining nodes of the non-empty list to the temporary node.
    • e. Return the next node of the dummy node.
  2. Define a function mergeSort that takes three arguments – a vector of linked lists, a starting index, and an ending index. It performs merge sort on the linked lists from the starting index to the ending index.

    • a. If the starting index is equal to the ending index, return the linked list at that index.
    • b. Calculate the mid index and call mergeSort recursively on the left and right halves of the vector.
    • c. Merge the two sorted linked lists obtained from the recursive calls using the merge function and return the result.
  3. Define the main function mergeKLists that takes the vector of linked lists as input and returns a single sorted linked list.

    • a. If the input vector is empty, return a null pointer.
    • b. Call the mergeSort function on the entire input vector, from index 0 to index k-1, where k is the size of the input vector.
    • c. Return the merged linked list obtained from the mergeSort function call.
  4. End of algorithm.

				
					/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* merge(ListNode *left, ListNode *right) {
        ListNode *dummy = new ListNode(-1);
        ListNode *temp = dummy;
        while (left != nullptr && right != nullptr) {
            if (left -> val < right -> val) {
                temp -> next = left;
                temp = temp -> next;
                left = left -> next;
            }
            else {
                temp -> next = right;
                temp = temp -> next;
                right = right -> next;
            }
        }
        while (left != nullptr) {
            temp -> next = left;
            temp = temp -> next;
            left = left -> next;
        }
        while (right != nullptr) {
            temp -> next = right;
            temp = temp -> next;
            right = right -> next;
        }
        return dummy -> next;
    }
    ListNode* mergeSort(vector<ListNode*>& lists, int start, int end) {
        if (start == end) 
            return lists[start];
        int mid = start + (end - start) / 2;
        ListNode *left = mergeSort(lists, start, mid);
        ListNode *right = mergeSort(lists, mid + 1, end);
        return merge(left, right);
    }
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if (lists.size() == 0)
            return nullptr;
        return mergeSort(lists, 0, lists.size() - 1);
    }
};
				
			
CategoryDifficultyLikesDislikes
algorithmsMedium (38.65%)170864353
Tags

Companies

permutation of an array of integers is an arrangement of its members into a sequence or linear order.

  • For example, for arr = [1,2,3], the following are all the permutations of arr[1,2,3], [1,3,2], [2, 1, 3], [2, 3, 1], [3,1,2], [3,2,1].

The next permutation of an array of integers is the next lexicographically greater permutation of its integer. More formally, if all the permutations of the array are sorted in one container according to their lexicographical order, then the next permutation of that array is the permutation that follows it in the sorted container. If such arrangement is not possible, the array must be rearranged as the lowest possible order (i.e., sorted in ascending order).

  • For example, the next permutation of arr = [1,2,3] is [1,3,2].
  • Similarly, the next permutation of arr = [2,3,1] is [3,1,2].
  • While the next permutation of arr = [3,2,1] is [1,2,3] because [3,2,1] does not have a lexicographical larger rearrangement.

Given an array of integers numsfind the next permutation of nums.

The replacement must be in place and use only constant extra memory.

 

Example 1:

Input: nums = [1,2,3]
Output: [1,3,2]

Example 2:

Input: nums = [3,2,1]
Output: [1,2,3]

Example 3:

Input: nums = [1,1,5]
Output: [1,5,1]

 

Constraints:

  • 1 <= nums.length <= 100
  • 0 <= nums[i] <= 100

Approach:

Intuition

We can solve this question using 3 ways.

  1. Find all the permutation of Array(nums) then we can easily find next permutation.
  2. Solved using Array + Two Pointers.
  3. Solved using next_permutation (inbuilt) function.

Approach

We can easily understand the All the approaches by seeing the code which is easy to understand with comments.

Complexity

  • Time complexity:

Time Complexity : O(N), Since we traverse the entire Array(nums) once in the worst case. Where N = size of the Array(nums).

  • Space complexity:

Space Complexity : O(1), Constant Space.

				
					/*

    Time Complexity : O(N), Since we traverse the entire Array(nums) once in the worst case. Where N = size of
    the Array(nums).

    Space Complexity : O(1), Constant Space.

    Solved using Array + Two Pointers.

*/


/***************************************** Approach 1 First Code *****************************************/

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int n = nums.size(), index = -1;
        for(int i=n-2; i>=0; i--){
            if(nums[i] < nums[i+1]){
                index = i;
                break;
            }
        }
        for(int i=n-1; i>=index && index != -1; i--){
            if(nums[i] > nums[index]){
                swap(nums[i], nums[index]);
                break;
            }
        }
        reverse(nums.begin() + index + 1, nums.end());
    }
};






/***************************************** Approach 1 Second Code *****************************************/

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        next_permutation(nums.begin(), nums.end());
    }
};
				
			
CategoryDifficultyLikesDislikes
algorithmsHard (60.00%)29359421
Tags

Companies

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

 

Example 1:

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.

Example 2:

Input: height = [4,2,0,3,2,5]
Output: 9

 

Constraints:

  • n == height.length
  • 1 <= n <= 2 * 104
  • 0 <= height[i] <= 105

Approach:

Approach

  • Here the approach is like we basically find the left max and right max and based on that we start our movement in two pointer , first have a glance at the below depicted figure which is later followed by explaination.

 

  • As shown in the figure we start with finding the left most height and the right most height and then we do left++ , right– and continue. Now if the new left height is greater than max left height then we update the lmax height and similarly for the right side.
  • When This is not the case the we proceed with the side with the minimum height , say it’s left for the further understanding , now we take the difference b/w the left heights and add to the water stored i.ei.e water += lmax - height[lpos]; or water += rmax - height[rpos]; according to the current scenario as explained above.
  • In the same way depicted above we further continue till the loop i.ei.e ends while(lpos <= ros) then we would finally obtain the water which can be trapped during this process.
				
					class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        int lmax = height[0];
        int rmax = height[n-1];
        int lpos = 1;
        int rpos = n-2;
        int water = 0;
        while(lpos <= rpos)
        {
            if(height[lpos] >= lmax)
            {
                lmax = height[lpos];
                lpos++;
            }
            else if(height[rpos] >= rmax)
            {
                rmax = height[rpos];
                rpos--;
            }
            else if(lmax <= rmax && height[lpos] < lmax)
            {
                water += lmax - height[lpos];
                lpos++;
            }
            else
            {
                water += rmax - height[rpos];
                rpos--;
            }
        
        }
        return water;
    }
};
				
			
CategoryDifficultyLikesDislikes
algorithmsHard (27.28%)7762318
Tags

Companies

Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for '?' and '*' where:

  • '?' Matches any single character.
  • '*' Matches any sequence of characters (including the empty sequence).

The matching should cover the entire input string (not partial).

 

Example 1:

Input: s = "aa", p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".

Example 2:

Input: s = "aa", p = "*"
Output: true
Explanation: '*' matches any sequence.

Example 3:

Input: s = "cb", p = "?a"
Output: false
Explanation: '?' matches 'c', but the second letter is 'a', which does not match 'b'.

 

Constraints:

  • 0 <= s.length, p.length <= 2000
  • s contains only lowercase English letters.
  • p contains only lowercase English letters, '?' or '*'.

Approach:

Approach

solvetab Function: This function uses the tabulation technique to find if the string s matches the wildcard pattern p. It initializes two vectors, prev and curr, of size p.length() + 1. These vectors are used to represent the DP table.

Base Case Initialization: It sets prev[0] to true, representing an empty string matching an empty pattern.

Handling the ” Characters at the Start of Pattern: It checks if the pattern starts with multiple ” characters. For each character in p from 1 to p.length(), it sets prev[j] to true if the pattern contains only ‘*’ characters from the start.

Filling DP Table: It iterates through each character in s and each character in p, starting from 1 to s.length() and 1 to p.length(). For each character, it checks two conditions:

If the characters are the same or if the pattern has a ‘?’, it propagates the result from the previous diagonal position (prev[j-1]) to the current position (curr[j]).
If the pattern has a ”, it propagates the result from the previous row (prev[j]) or the previous column (curr[j-1]) to the current position (curr[j]), indicating that the ” can match either a single character in s or a sequence of characters.
Final Result: After filling the DP table, the function returns the value at prev[p.length()], which indicates if the entire string s matches the entire wildcard pattern p.

isMatch Function: This function serves as an interface to call the solvetab function. It takes the input strings s and p and calls solvetab(s, p) to find if s matches p

Complexity

  • Time complexity:0(M*N)
  • Space complexity:0(N)
				
					class Solution {
public:

bool solvetab(string s, string p)
{
    vector<vector<int>>dp(s.length()+1,vector<int>(p.length()+1,0));
    dp[0][0]=true;
    for(int j=1;j<=p.length();j++)
    {
    bool flag= true;
        for(int k =1;k<=j;k++)
        {
            if(p[k-1]!='*')
            {
                flag=false;
                break;
            }
        }
        dp[0][j]=flag;
    }
    for(int i =1;i<=s.length();i++)
    {
        for(int j =1;j<=p.length();j++)
        {
            if(p[j-1]=='?' || p[j-1]==s[i-1])
            {
                dp[i][j]=dp[i-1][j-1];
            }
            else if(p[j-1]=='*')
            {
              dp[i][j]=dp[i-1][j] || dp[i][j-1];
            }
            else
            {
                  dp[i][j]=false;
            }
        }
    }
    return dp[s.length()][p.length()];
}




    bool isMatch(string s, string p)
    {
       
        // return solve(s,p,s.length()-1,p.length()-1,dp);
return solvetab(s,p);
    }
};
				
			
CategoryDifficultyLikesDislikes
algorithmsMedium (34.04%)88758711
Tags

Companies

Implement pow(x, n), which calculates x raised to the power n (i.e., xn).

 

Example 1:

Input: x = 2.00000, n = 10
Output: 1024.00000

Example 2:

Input: x = 2.10000, n = 3
Output: 9.26100

Example 3:

Input: x = 2.00000, n = -2
Output: 0.25000
Explanation: 2-2 = 1/22 = 1/4 = 0.25

 

Constraints:

  • -100.0 < x < 100.0
  • -231 <= n <= 231-1
  • n is an integer.
  • Either x is not zero or n > 0.
  • -104 <= xn <= 104

Approach:

Intuition

We can solve this question using math and recursion.

Approach

We can easily understand the all the approaches by seeing the code which is easy to understand with comments.

Complexity

  • Time complexity:

Time complexity is given in code comment.

  • Space complexity:

Space complexity is given in code comment.

				
					/*

    Time Complexity : O(N), because we call the recurtion until we multiply the base exponent times. Thus the
    time complexity is linear.

    Space Complexity : O(N), Recursion stack space.

*/


/***************************************** Approach 1 *****************************************/

class Solution {
private:
    double power(double x, int n){
        if(n==0){
            return 1;
        }
        return x * power(x, n-1);
    }
public:
    double myPow(double x, int n) {
        if (n == INT_MAX) return (x == 1) ? 1 : (x == -1) ? -1 : 0;
        if (n == INT_MIN) return (x == 1 || x == -1) ? 1 : 0;
        double num = 1;
        if(n>=0){
            num = power(x, n);
        }
        else{
            n = -n;
            num = power(x, n);
            num = 1.0/num;
        }
        return num;
    }
};






/*

    Time Complexity : O(N), because we loop until we multiply the base exponent times. Thus the time complexity
    is linear.

    Space Complexity : O(1), Constant space.

*/


/***************************************** Approach 2 *****************************************/

class Solution {
public:
    double myPow(double x, int n) {
        if (n == INT_MAX) return (x == 1) ? 1 : (x == -1) ? -1 : 0;
        if (n == INT_MIN) return (x == 1 || x == -1) ? 1 : 0;
        double num = 1;
        if(n>=0){
            while(n>0){
                num *= x;
                n--;
            }
        }
        else{
            n = -n;
            while(n>0){
                num *= x;
                n--;
            }
            num = 1.0/num;
        }
        return num;
    }
};






/*

    Time Complexity : O(logN).

    Space Complexity : O(logN), Recursion stack space.

*/


/***************************************** Approach 3 *****************************************/

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);
        }
    }
};






/*

    Time Complexity : O(logN).

    Space Complexity : O(1), Constant space.

*/


/***************************************** Approach 4 *****************************************/

class Solution {
public:
    double myPow(double x, int n) {
        double num = 1;
        long long nn = n;
        if(nn < 0) nn = -nn;
        while(nn>0){
            if(nn%2==1){
                num = num * x;
                nn--;
            }
            else{
                x = x*x;
                nn/=2;
            }
        }
        if(n < 0){
            num = 1.0/num;
        }
        return num;
    }
};






/*

    Time Complexity : O(logN).

    Space Complexity : O(logN), Constant space.

*/


/***************************************** Approach 5 *****************************************/

class Solution {
public:
    double myPow(double x, int n) {
        return pow(x, n);
    }
};