Day 17 (30 Days of Code)

18 July 2023

I solved 2 Leetcode problems.

• Is Subsequence

My approach:

I already knew there exist a very easy solution for this question by using two pointer method. However, I also felt like solving through memoization which gave me an error of memory limit.

My solution:

• Two Pointer Method

bool isSubsequence(string s, string t) {
        int n = s.size();
        int m = t.size();

        int i = 0;
        int j = 0;

        while(i<n && j<m){
            if(s[i]==t[j]){
                i++;
            }
            j++;
        }

        if(i==n){
            return true;
        }
        return false;

    }
};

• Memoization

int helper(string s, string t,int **arr){

        int n = s.size();
        int m = t.size();

        if(s.size()==0){
            return 1;
        }
        if(t.size()==0){
            return 0;
        }

        if(arr[n][m]!=-1){
            return arr[n][m];
        }

        int ans;
        if(s[0]==t[0]){
            ans = isSubsequence(s.substr(1), t.substr(1));
        }else{
            ans = isSubsequence(s, t.substr(1));
        }

        arr[n][m] = ans;
        return ans;
    }

    bool isSubsequence(string s, string t) {
        int n = s.size();
        int m = t.size();

        int ** arr = new int*[n+1];

        for(int i=0;i<=n;i++){
            arr[i] = new int[m+1];
        }

        for(int i=0;i<=n;i++){
            for(int j=0;j<=m;j++){
                arr[i][j] = -1;
            }
        }

        return helper(s,t,arr);

   }

• Valid Perfect Square

My approach:

I was able to figure out that the binary search would be used but I had trouble implementing it. So I had to refer to the hints.

My solution:

class Solution {
public:
    bool isPerfectSquare(int num) {

        if(num==1){
            return true;
        }        

        int org = num;

        int e = num/2;
        int s = 0;

        while(s<=e){
            long long int mid = s+(e-s)/2;
            if(mid*mid>num){
                e = mid-1;
            }
            else if(mid*mid<num){
                s = mid+1;
            }
            else{
                return true;
            }
        }
        return false;
    }
};