Isomorphic Strings

Given two strings s and t, determine if they are isomorphic.

Two strings are isomorphic if the characters in s can be replaced to get t.

All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character but a character may map to itself.

For example,
Given "egg", "add", return true.

Given "foo", "bar", return false.

Given "paper", "title", return true.

Note:
You may assume both s and t have the same length.

My solution:


#include<iostream>

#include<string>

#include<array>

using namespace std;

class Solution {

public:

        //compute code : egg maps to 10,20,20,  ddeea maps to 20;20;21;21;10

            //if two string are isomorphic iff they have same code       

            //input string s, output code



    void compute_code(string s, int code[], int N){

          int occur[N+1];

          for(int i=0;i<N+1;i++){

            occur[i]=0;

          }

          for(int i=0;i<N;i++){

            code[i]=0;

          }

          for(int i=0;i<s.size();i++){

            if(code[i]==0){

                //count the number of occurence of s[i]

                int counter=1;

                for (int j=i+1;j<s.size();j++){

                    if(s[j]==s[i]){counter++;}

                }

                int code_nr = 10*counter+occur[counter];

                occur[counter]++;

                for(int j=i;j<N;j++){

                    if(s[j]==s[i]){code[j]=code_nr;}

                }   

            }   

          }   

        return;    

    }   

    bool isIsomorphic(string s, string t) { 

         if(s.size()!=t.size())return false;



          int N = s.size();

          int code_s[N];

          int code_t[N];

          compute_code(s,code_s,N);

          compute_code(t,code_t,N);

          for(int i=0;i<N;i++){

            if(code_s[i]!=code_t[i]){return false;}

          }

          return true;

    }      

};

int main(){

    string s="add";

    string t="egg";

    Solution S;

    bool result = S.isIsomorphic(s,t);

    cout<<result<<endl;

    return 0;

}

Gas Station

There are N gas stations along a circular route, where the amount of gas at station i is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.

Return the starting gas station’s index if you can travel around the circuit once, otherwise return -1.

Note:
The solution is guaranteed to be unique.

My solution: Started with a brutal force solution, then optimized it to the following linear solution. Finally got it right! 😀

class Solution {
public:
 int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {

int N=gas.size();
int try_start=0;
do{
int gas_left=0;
int j=0;
for( j=0;j<N;j++){
    gas_left+=gas[(try_start+j)%N]-cost[(try_start+j)%N];
    if(gas_left<0){
        try_start+=j+1;
        break;
    }
}
//cout<<j<<endl;
if(j==N) {return try_start;}
}while(try_start<N);
return try_start<N ? try_start: -1;
 }
};

Unique Binary Search Trees

Given n, how many structurally unique BST’s (binary search trees) that store values 1…n?

For example,
Given n = 3, there are a total of 5 unique BST’s.

 

My solution: This solution uses recursion. It can be modified to use dynamic programming to achieve higher efficiency at the cost of extra space.

class Solution {
public:
    int numTrees(int n) {
        if(n<0) return -1;
        if(n==0) return 1;
        else{
            int result=0;
            for(int r=0;r<n;r++){
                result=result+numTrees(r)*numTrees(n-r-1);
            }
            return result;
        }

    }
};

Remove Duplicates from Sorted List

Given a sorted linked list, delete all duplicates such that each element appear only once.

For example,
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.

My solution:


class Solution {
public:
 ListNode *deleteDuplicates(ListNode *head) {
 
 if(head!=NULL){
 int value=head->val;
 struct ListNode* current_pt=head;
 struct ListNode* temp_pt;
 while(current_pt->next!=NULL){
 
 if(current_pt->next->val!=value){
 value=current_pt->next->val;
 current_pt=current_pt->next; 
 }
 else {
 temp_pt=current_pt->next;
 current_pt->next=current_pt->next->next;
 free(temp_pt);
 }
 
 }
 }
 return head;
 
 
 
 }
};

Valid Parentheses

Valid Parentheses

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

The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

My solution: make use of a stack


#include<iostream>
#include<string>
#include<stack>
#include<map>

using namespace std;
class Solution{
public:
    bool isValid(string s){
        map<char,char> par_map;
        par_map['(']=')';
        par_map['[']=']';
        par_map['{']='}';
        stack<char> mystack;
        

        if(s.size()==0){return true;}
        char c;
        for(int i=0;i<s.size();i++){  
            c=s[i];
            if (c=='(' || c=='[' || c== '{')
                mystack.push(c);
            if (c==')'|| c==']' || c== '}'){
                if(mystack.empty()) return false;
                else{
                if (par_map[mystack.top()]!=c)
                {return false;}
                else{
                    mystack.pop();
                }
                }
            }
        }
        
          return mystack.empty();
          return true;

}
};

int main()
{
   Solution sl;
   cout<<sl.isValid("([])(){[}")<<endl;
}