喜刷刷: algorithm

Showing posts with label algorithm. Show all posts

Saturday, November 29, 2014

[LeetCode] Regular Expression Matching

Implement regular expression matching with support for '.' and '*'.

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

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

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true

思路1: DP

关键在于如何处理这个'*'号。

状态：和Mininum Edit Distance这类题目一样。

dp[i][j]表示s[0:i-1]是否能和p[0:j-1]匹配。

递推公式：由于只有p中会含有regular expression，所以以p[j-1]来进行分类。

p[j-1] != '.' && p[j-1] != '*'：dp[i][j] = dp[i-1][j-1] && (s[i-1] == p[j-1])

p[j-1] == '.'：dp[i][j] = dp[i-1][j-1]

而关键的难点在于 p[j-1] = '*'。由于星号可以匹配0，1，乃至多个p[j-2]。

1. 匹配0个元素，即消去p[j-2]，此时p[0: j-1] = p[0: j-3]

dp[i][j] = dp[i][j-2]

2. 匹配1个元素，此时p[0: j-1] = p[0: j-2]

dp[i][j] = dp[i][j-1]

3. 匹配多个元素，此时p[0: j-1] = { p[0: j-2], p[j-2], ... , p[j-2] }

dp[i][j] = dp[i-1][j] && (p[j-2]=='.' || s[i-2]==p[j-2])

class Solution {
public:
    bool isMatch(const char *s, const char *p) {
        int m = strlen(s), n = strlen(p);
        vector<vector<bool>> dp(m+1, vector<bool>(n+1,false));
        dp[0][0] = true;
        
        for(int i=0; i<=m; i++) {
            for(int j=1; j<=n; j++) {
                if(p[j-1]!='.' && p[j-1]!='*') {
                    if(i>0 && s[i-1]==p[j-1] && dp[i-1][j-1])
                        dp[i][j] = true;
                }
                else if(p[j-1]=='.') {
                    if(i>0 && dp[i-1][j-1])
                        dp[i][j] = true;
                }
                else if(j>1) {  //'*' cannot be the 1st element
                    if(dp[i][j-1] || dp[i][j-2])  // match 0 or 1 preceding element
                        dp[i][j] = true;
                    else if(i>0 && (p[j-2]==s[i-1] || p[j-2]=='.') && dp[i-1][j]) // match multiple preceding elements
                        dp[i][j] = true;
                }
            }
        }
        return dp[m][n];
    }
};

思路2: 双指针扫描

LeetCode作者给的解法，非常巧妙：

http://leetcode.com/2011/09/regular-expression-matching.html

Thursday, November 27, 2014

[LeetCode] Word Ladder I, II

Word Ladder I

Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:

Only one letter can be changed at a time
Each intermediate word must exist in the dictionary

For example,

Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]

As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

Note:

Return 0 if there is no such transformation sequence.
All words have the same length.
All words contain only lowercase alphabetic characters.

Word Ladder II

Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) from start to end, such that:

Only one letter can be changed at a time
Each intermediate word must exist in the dictionary

For example,

Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]

Return

  [
    ["hit","hot","dot","dog","cog"],
    ["hit","hot","lot","log","cog"]
  ]

Note:

All words have the same length.
All words contain only lowercase alphabetic characters.

思路：

LeetCode中为数不多的考图的难题。尽管题目看上去像字符串匹配题，但从“shortest transformation sequence from start to end”还是能透露出一点图论中最短路径题的味道。如何转化？

1. 将每个单词看成图的一个节点。
2. 当单词s1改变一个字符可以变成存在于字典的单词s2时，则s1与s2之间有连接。
3. 给定s1和s2，问题I转化成了求在图中从s1->s2的最短路径长度。而问题II转化为了求所有s1->s2的最短路径。

无论是求最短路径长度还是求所有最短路径，都是用BFS。在BFS中有三个关键步骤需要实现:

1. 如何找到与当前节点相邻的所有节点。
这里可以有两个策略：
(1) 遍历整个字典，将其中每个单词与当前单词比较，判断是否只差一个字符。复杂度为：n*w，n为字典中的单词数量，w为单词长度。
(2) 遍历当前单词的每个字符x，将其改变成a~z中除x外的任意一个，形成一个新的单词，在字典中判断是否存在。复杂度为：26*w，w为单词长度。
这里可以和面试官讨论两种策略的取舍。对于通常的英语单词来说，长度大多小于100，而字典中的单词数则往往是成千上万，所以策略2相对较优。

2. 如何标记一个节点已经被访问过，以避免重复访问。
可以将访问过的单词从字典中删除。

3. 一旦BFS找到目标单词，如何backtracking找回路径？

Word Ladder I

class Solution {
public:
    int ladderLength(string start, string end, unordered_set<string> &dict) {
        dict.insert(end);
        queue<pair<string,int>> q;
        q.push(make_pair(start,1));
        while(!q.empty()) {
            string s = q.front().first;
            int len = q.front().second;
            if(s==end) return len;
            q.pop();
            vector<string> neighbors = findNeighbors(s, dict);
            for(int i=0; i<neighbors.size(); i++) 
                q.push(make_pair(neighbors[i],len+1));
        }
        return 0;
    }
    
    vector<string> findNeighbors(string s, unordered_set<string> &dict) {
        vector<string> ret;
        for(int i=0; i<s.size(); i++) {
            char c = s[i];
            for(int j=0; j<26; j++) {
                if(c=='a'+j) continue;
                s[i] = 'a'+j;
                if(dict.count(s)) {
                    ret.push_back(s);    
                    dict.erase(s);    
                }
            }
            s[i] = c;
        }
        return ret;
    }
};

Word Ladder II

[LeetCode新题] Intersection of Two Linked Lists

Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

A:          a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗            
B:     b1 → b2 → b3

begin to intersect at node c1.

Notes:

If the two linked lists have no intersection at all, return null.
The linked lists must retain their original structure after the function returns.
You may assume there are no cycles anywhere in the entire linked structure.
Your code should preferably run in O(n) time and use only O(1) memory.

思路：

找链表交界，很类似Linked List Cycle II那题，方法也是类似的双指针相遇法。分两步走：

1. 如何判断两链表是否相交？

两链表相交则他们必然有共同的尾节点。所以遍历两两链表，找到各自的尾节点，如果tailA!=tailB则一定不相交，反之则相交。

2. 如何判断两链表相交的起始节点？

在第1步判断相交时可以顺带计算两链表的长度lenA和lenB。让长的链表的head先走abs(lenA-lenB)步，然后和短链表的head一起走，直到两者相遇，即为要找的节点。

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if(!headA || !headB) return NULL;
        int lenA = 0, lenB = 0;
        ListNode *tailA = headA, *tailB = headB;
        
        while(tailA->next) {
            tailA = tailA->next;
            lenA++;
        }
        while(tailB->next) {
            tailB = tailB->next;
            lenB++;
        }
        if(tailA!=tailB) return NULL;
        
        if(lenA>lenB) {
            for(int i=0; i<lenA-lenB; i++)
                headA = headA->next;
        }
        else {
            for(int i=0; i<lenB-lenA; i++)
                headB = headB->next;
        }
        
        while(headA!=headB) {
            headA = headA->next;
            headB = headB->next;
        }
        
        return headA;
    }
};

[LeetCode] First Missing Positive

Given an unsorted integer array, find the first missing positive integer.

For example,
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.

Your algorithm should run in O(n) time and uses constant space.

思路：

无序数组的题目如果要O(n)解法往往要用到hash table，但这题要求constant space。所以可以用数组本身作为一个"hash table"：A[0] = 1, A[1] = 2, .... A[n-1] = n。目标是尽可能将数字i放到数组第i-1个位置。

扫描数组中每个数：
1. 如果A[i]<1或者A[i]>n。说明A[i]一定不是first missing positive。跳过
2. 如果A[i] = i+1，说明A[i]已经在正确的位置，跳过
3. 如果A[i]!=i+1，且0<A[i]<=n，应当将A[i]放到A[A[i]-1]的位置，所以可以交换两数。
这里注意，当A[i] = A[A[i]-1]时会陷入死循环。这种情况下直接跳过。

class Solution {
public:
    int firstMissingPositive(int A[], int n) {
        int i=0;
        while(i<n) {
            if(A[i]!=i+1 && A[i]>0 && A[i]<=n && A[i]!=A[A[i]-1])
                swap(A[i],A[A[i]-1]);
            else
                i++;
        }
        for(int i=0; i<n; i++) {
            if(A[i]!=i+1) return i+1;
        }
        return n+1;
    }
};

Wednesday, November 26, 2014

[LeetCode] Merge Intervals

Given a collection of intervals, merge all overlapping intervals.

For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].

思路：

从Insert Interval那题的解法，我们知道了如何判断两个interval是否重合，如果不重合，如何判断先后顺序。那么这题就很简单了，首先按照start的大小来给所有interval排序，start小的在前。然后扫描逐个插入结果。如果发现当前interval a和结果中最后一个插入的interval b不重合，则插入a到b的后面；反之如果重合，则将a合并到b中。注意要给object排序需要定义一个compare structure作为sort函数的额外参数。

class Solution {
public:
    struct compInterval {
        bool operator()(const Interval &a, const Interval &b) const {
            return a.start<b.start;
        }
    };

    vector<Interval> merge(vector<Interval> &intervals) {
        sort(intervals.begin(),intervals.end(),compInterval());
        vector<Interval> ret;
        for(int i=0; i<intervals.size(); i++) {
            if(ret.empty() || ret.back().end < intervals[i].start)  // no overlap
                ret.push_back(intervals[i]);
            else   // overlap
                ret.back().end = max(ret.back().end, intervals[i].end);
        }
        return ret;
    }
};

[LeetCode] Insert Interval

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

Example 1:
Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].

Example 2:
Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].

This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].

思路：

题目涉及两个问题：

1. 如何判断两个interval有重合。

2. 如果重合，如何合并。

3. 如何判断[s1, e1]是否在[s2, e2]前面

A1. 两个interval有重合有很多种可能性，但判断它们不重合则比较简单直观。无非两种情况：

(1) [s1, e1] [s2, e2]：即s2>e1

(2) [s2, e2] [s1, e1]：即s1>e2

不重合的条件为：s2>e1 || s1>e2，反之则重合。

A2. 对于两个有重合的interval： [s1, e1]，[s2, e2]。合并后变为[min(s1,s2), max(e1,e2)]。

A3. [s1, e1]在[s2, e2]前面的条件：e1<s2

所以插入interval a的算法为：扫描队列中每个interval I[i]：
如果a已经被插入了，则只要插入I(i)就行。
如果a在I(i)前，则先插入a再插入I(i)到结果。

如果a和I(i)有重合，则将I(i)合并入a，但并不插入结果。

如果a在I(i)后，则插入I(i)到结果。

class Solution {
public:
    vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) {
        vector<Interval> ret;
        bool isInsert = false;
        for(int i=0; i<intervals.size(); i++) {
            // already insert newInterval
            if(isInsert) {  
                ret.push_back(intervals[i]);
                continue;
            }
            
            // insert newInterval before current interval
            if(newInterval.end < intervals[i].start) {  
                ret.push_back(newInterval);
                ret.push_back(intervals[i]);
                isInsert = true;
                continue;
            }
            
            // combine newInterval with current interval
            if(newInterval.start<=intervals[i].end && intervals[i].start<=newInterval.end) {
                newInterval.start = min(newInterval.start, intervals[i].start);
                newInterval.end = max(newInterval.end, intervals[i].end);
                continue;
            }
            
            // newInterval after current interval
            ret.push_back(intervals[i]);
        }
        
        if(!isInsert) ret.push_back(newInterval);
        return ret;
    }
};

[LeetCode] Longest Valid Parentheses

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

For "(()", the longest valid parentheses substring is "()", which has length = 2.

Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.

思路1：DP

求极值问题一般想到DP或Greedy，显然Greedy在这里不太适用，只有用DP了。

1. 状态：
DP[i]：以s[i-1]为结尾的longest valid parentheses substring的长度。

2. 通项公式：
s[i] = '('：
DP[i] = 0

s[i] = ')'：找i前一个字符的最长括号串DP[i]的前一个字符j = i-2-DP[i-1]
DP[i] = DP[i-1] + 2 + DP[j]，如果j >=0，且s[j] = '('
DP[i] = 0，如果j<0，或s[j] = ')'

......... ( x x x x )
j i-2 i-1

证明：不存在j' < j，且s[j' : i]为valid parentheses substring。
假如存在这样的j'，则s[j'+1 : i-1]也valid。那么对于i-1来说：
( x x x x x
j' j'+1 i-1
这种情况下，i-1是不可能有比S[j'+1 : i-1]更长的valid parentheses substring的。

3. 计算方向
显然自左向右，且DP[0] = 0

class Solution {
public:
    int longestValidParentheses(string s) {
        int n = s.size(), maxLen = 0;
        vector<int> dp(n+1,0);
        for(int i=1; i<=n; i++) {
            int j = i-2-dp[i-1];
            if(s[i-1]=='(' || j<0 || s[j]==')') 
                dp[i] = 0;
            else {
                dp[i] = dp[i-1]+2+dp[j];
                maxLen = max(maxLen, dp[i]);
            }
        }
        return maxLen;
    }
};

思路2：stack

括号题自然又想到了stack。仔细想下，这题目其实是Valid Parentheses的升级版。一个valid parentheses substring必然以'('开头以')'结尾，并且中间一定也是一个valid parentheses substring。这也意味着依照Valid Parentheses解法那样，用stack来存储没有配对的'('和')'，并用相应的')'来消去stack top的'('，最长substring的首尾必然会在这个过程中相消。

1. 由于我们需要知道它们之间的长度，所以stack里可以存储各个'('的坐标。
2. 为了能正确计算类似“ ) ( ) ( ) ”这种valid substring连接而组成的valid substring。我们必须也插入')'进stack，作为边界来计算长度。
3. 为了能在stack中区分左右括号，每个插入item定义为pair<int,int>。first为坐标，second表示左还是右括号。

class Solution {
public:
    int longestValidParentheses(string s) {
        stack<pair<int,int>> stk;   // first: index, second: 0:'(', 1:')'
        int maxLen = 0, curLen = 0;
        for(int i=0; i<s.size(); i++) {
            if(s[i]=='(')   // left parenthesis
                stk.push(make_pair(i,0));
            else {          // right parenthesis
                if(stk.empty() || stk.top().second==1)
                    stk.push(make_pair(i,1));
                else {
                    stk.pop();
                    if(stk.empty())
                        curLen = i+1;
                    else
                        curLen = i-stk.top().first;    
                    maxLen = max(maxLen, curLen);
                }
            }
        }
        return maxLen;
    }
};

[LeetCode] Largest Rectangle in Histogram

Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

The largest rectangle is shown in the shaded area, which has area = 10 unit.

For example,
Given height = [2,1,5,6,2,3],
return 10.

思路1：Brute Force

对每个bar i，求它能构成的最大面积。用左右指针向两边扫，直到遇到比bar i矮的或遇到边界则停止，然后根据左右指针距离得到宽度和面积。但是这个解法过不了大集合，因为最坏情况：当整个histogram是递增或递减时，算法复杂度是O(n^2)。

class Solution {
public:
    int largestRectangleArea(vector<int> &height) {
        int maxArea = 0;
        for(int i=0; i<height.size(); i++) 
            maxArea = max(maxArea, calRecArea(height,i));
        return maxArea;
    }
    
    int calRecArea(vector<int> &height, int index) {
        int left = index-1, right = index+1;
        while(left>=0 && height[left]>=height[index]) 
            left--;
        while(right<height.size() && height[right]>=height[index])
            right++;
            
        return (right-left-1)*height[index];
    }
};

思路2：Stack

仔细考察Brute Force算法，发现问题在于指针重复扫描。以递增序列为例：

0 1 2 3 4 5 6

在计算s[0]的时候扫描了右边6个数，计算s[1]时继续扫描右边5个数，依次类推。而没能利用到这个序列的递增性质。当序列从i递增到j时，bar i~j的面积一定都能扩展到j。而一旦在j+1递减了，那么表示bar i~j中的部分bar k无法继续扩展，条件是h[k]>h[j+1]。

1. 利用这个性质，可以将递增序列cache在一个stack中，一旦遇到递减，则根据h[j+1]来依次从stack里pop出那些无法继续扩展的bar k，并计算面积。

2. 由于面积的计算需要同时知道高度和宽度，所以在stack中存储的是序列的坐标而不是高度。因为知道坐标后很容易就能知道高度，而反之则不行。

class Solution {
public:
    int largestRectangleArea(vector<int> &height) {
        if(height.empty()) return 0;
        height.push_back(-1);
        height.insert(height.begin(),-1);
        stack<int> s;
        int maxArea = 0;
        
        for(int i=0; i<height.size(); i++) {
            while(!s.empty() && height[i]<=height[s.top()]) {
                int h = height[s.top()];
                s.pop();
                if(height[i]<h) maxArea = max(maxArea, (i-s.top()-1)*h);
            }
            s.push(i);
        }
        
        // reset height
        height.erase(height.begin());
        height.pop_back();
        return maxArea;
    }
};

[LeetCode] Unique Binary Search Trees I, II

Unique Binary Search Trees I

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.

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

Unique Binary Search Trees II

Given n, generate all structurally unique BST's (binary search trees) that store values 1...n.

For example,
Given n = 3, your program should return all 5 unique BST's shown below.

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

思路: Unique Binary Search Trees I

首先注意这里是BST而不是普通的Binary Tree，所以数字会对插入的位置有影响。这类找combination/permutation的题都需要找找规律。

n = 0

n = 1

n = 2

1 2

\ /

2 1

n = 3

1 3 3 2 1

\ / / / \ \

3 2 1 1 3 2

/ / \ \

2 1 2 3

定义f(n)为unique BST的数量，以n = 3为例：

构造的BST的根节点可以取{1, 2, 3}中的任一数字。

如以1为节点，则left subtree只能有0个节点，而right subtree有2, 3两个节点。所以left/right subtree一共的combination数量为：f(0) * f(2) = 2

以2为节点，则left subtree只能为1，right subtree只能为2：f(1) * f(1) = 1

以3为节点，则left subtree有1, 2两个节点，right subtree有0个节点：f(2)*f(0) = 2

总结规律：

f(0) = 1

f(n) = f(0)*f(n-1) + f(1)*f(n-2) + ... + f(n-2)*f(1) + f(n-1)*f(0)

class Solution {
public:
    int numTrees(int n) {
        vector<int> numBST(n+1,0);
        numBST[0] = 1;
        
        for(int i=1; i<=n; i++) {
            for(int j=0; j<i; j++) {
                numBST[i] += numBST[j]*numBST[i-1-j];
            }
        }
        return numBST[n];
    }
};

思路: Unique Binary Search Trees II

要求生成所有的unique BST，类似combination/permutation的题目，可以递归构造。

1. 根节点可以任取min ~ max (例如min = 1, max = n)，假如取定为i。

2. 则left subtree由min ~ i-1组成，假设可以有L种可能。right subtree由i+1 ~ max组成，假设有R种可能。生成所有可能的left/right subtree。

3 对于每个生成的left subtree/right subtree组合<T_left(p), T_right(q)>，p = 1...L，q = 1...R，添加上根节点i而组成一颗新树。

class Solution {
public:
    vector<TreeNode *> generateTrees(int n) {
        return genBST(1, n);
    }
    
    vector<TreeNode *> genBST(int min, int max) {
        vector<TreeNode *> ret;
        if(min>max) {
            ret.push_back(NULL);
            return ret;
        }
        
        for(int i=min; i<=max; i++) {
            vector<TreeNode*> leftSubTree = genBST(min,i-1);
            vector<TreeNode*> rightSubTree = genBST(i+1,max);
            for(int j=0; j<leftSubTree.size(); j++) {
                for(int k=0; k<rightSubTree.size(); k++) {
                    TreeNode *root = new TreeNode(i);
                    root->left = leftSubTree[j];
                    root->right = rightSubTree[k];
                    ret.push_back(root);
                }
            }
        }
        
        return ret;
    }
};

[LeetCode] Distinct Subsequences

Given a string S and a string T, count the number of distinct subsequences of T in S.

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE" is a subsequence of "ABCDE" while "AEC" is not).

Here is an example:
S = "rabbbit", T = "rabbit"

Return 3.

思路：

一看要求解的个数，然后又是string匹配，而且形式上和Minimum Edit Distance那题很像，基本就是DP题跑不了了。DP题惯例的三步走：定义状态，推导递推公式，确定状态计算方向和起始状态。

1. 状态：i, j分别表示T中长度为i的prefix：T[0:i-1]，和S中长度为j的prefix：S[0:j-1]。

DP[i][j]：S[0:j-1]中存在T[0:i-1]作为distinct subsequence的个数。显然如果j<i，DP[i][j] = 0。

2. 递推公式：

(a) T[i]!=s[j]:

T = r a b

S = r c a c b c

DP[i+1][j+1] = DP[i+1][j]

(b) T[i] = s[j]:

T = r a b b

S = r a b b b - DP[i+1][j] = 1

S = r a b b b - DP[i][j] = 2

S = r a b b b /

DP[i+1][j+1] = DP[i][j] + DP[i+1][j]

公式总结：
S[j-1]!= T[i-1]：DP[i][j] = DP[i][j-1]
S[j-1]==T[i-1]：DP[i][j] = DP[i-1][j-1] + DP[i][j-1]

3. 计算方向和起始状态：

DP[i][j]

DP[i+1][j] DP[i+1][j+1]

所以从上向下，从左到右的顺序可以计算。

根据计算顺序，需要先设置第0行、0列的值。
第0列：DP[i][0] = 0，i>0。因为T的长度大于S的长度，不可能成为S的subsequence。
第0行：DP[0][j] = 1，j>=0。这是为了保证第1行的计算正确：

T = r
S = r a r b r c

r a r b r c
1 1 1 1 1 1 1
r 0 1 1 2 2 3 3

4. 计算优化：用滚动数组减少内存消耗。

class Solution {
public:
    int numDistinct(string S, string T) {
        int n = S.size(), m = T.size();
        vector<int> dp(n+1, 1);
        
        for(int i=1; i<=m; i++) {
            int upLeft = dp[0];
            dp[0] = 0;
            for(int j=1; j<=n; j++) {
                int temp = dp[j];
                dp[j] = dp[j-1];
                if(S[j-1]==T[i-1]) dp[j] += upLeft;
                upLeft = temp;
            }
        }
        
        return dp[n];
    }
};