Leetcode 1641. Count Sorted Vowel Strings

Problem Link

We have to get the number of permutations we can have with using 5 vowels character in lexicographical order.

After every vowel character we can only take characters which are lexicographically equal or larger than it.
Suppose, we have a substring "aei" but we have to make the string size 4. But we can't take character "a" or "e", we forced to take character "i", "o", or "u".
For decrease the time complexity we used memoization technique with some extra memory space.

Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

class Solution { public: int memo[51][6]; int solve(int n,int i){ if(n==0){ return 1; } if(memo[n][i]!=0){ return memo[n][i]; } int forReturn = 0; for(int j=i;j<5;j++){ forReturn += solve(n-1,j); } memo[n][i] = forReturn; return memo[n][i]; } int countVowelStrings(int n) { return solve(n,0); } };

Leetcode 216. Combination Sum III ||Backtracking

 Problem Link

In this problem, we just have to generate a sum  S using K numbers. The numbers could be in a range of (1-9) we only can take a number once for a combination.

Solution Idea: Backtracking.  

Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

class Solution { public: vector<vector<int> > ans; int k,n; void fun(int numberUsed, int num, int sum,vector<int>vec,int flag[]){ if(numberUsed == k){ if(sum==n){ ans.push_back(vec); } } else if(numberUsed<k){ if(sum<n){ for(int i=num+1;i<=9;i++){ if(flag[i]==0 && sum+i<=n){ vec.push_back(i); flag[i]=1; fun(numberUsed+1,i,sum+i,vec,flag); vec.pop_back(); flag[i]=0; } } } } } vector<vector<int>> combinationSum3(int kk, int nn) { k = kk; n = nn; int flag[10]; memset(flag,0,sizeof flag); vector<int>vec; fun(0,0,0,vec,flag); return ans; } };

Leetcode 17. Letter Combinations of a Phone Number

Problem Link

In this problem we will be given a string of digits, as like old days featured phones. We have to generate the number of ways we can generate string if,

digit 2 = "abc"

digit 3 = "def"

....

digit 9 = "wxyz"

Solution idea:
we can use dfs  approach for solve this.

Code: 

 class Solution {  
 public:  
   map<char,string>mm;  
   vector<string>vec;  
   void solve(string digits,int pos,string ans){  
     if(pos == digits.size()){  
       if(digits!="")vec.push_back(ans);  
       return;  
     }  
     for(auto it:mm[digits[pos]]){  
       ans.push_back(it);  
       solve(digits,pos+1,ans);  
       ans.pop_back();  
     }      
   }  
   vector<string> letterCombinations(string digits) {  
     mm['2'] = "abc";  
     mm['3'] = "def";  
     mm['4'] = "ghi";  
     mm['5'] = "jkl";  
     mm['6'] = "mno";  
     mm['7'] = "pqrs";  
     mm['8'] = "tuv";  
     mm['9'] = "wxyz";  
     solve(digits,0,"");  
     return vec;  
   }  
 };