thảo luận Leetcode mỗi ngày

class Solution {
  public String removeStars(String s) {
    char[] stack = new char[s.length()];
    int head = 0;
    for (char c: s.toCharArray()) {
      if (c == '*') head--;
      else stack[head++] = c;
    }
    return new String(stack, 0, head);
  }
}

class Solution:
    def removeStars(self, s: str) -> str:
        stack = []
        for c in s:
            if c != '*':
                stack.append(c)
            else:
                stack.pop()
        return ''.join(stack)

class Solution:
    def simplifyPath(self, path: str) -> str:
        units = path.split('/')
        stack = []
        for u in units:
            if u == '' or u == '/' or u == '.':
                continue
            if u == '..':
                if len(stack) > 0:
                    stack.pop(-1)
                continue
            stack.append(u)

        return '/' + '/'.join(stack)

function simplifyPath(path: string): string {
    const stack: string[] = [];

    for (const s of path.split('/')) {
        if (s === '..') {
            stack.pop();
        } else if (s !== '' && s !== '.') {
            stack.push(s);
        }
    }

    return `/${stack.join('/')}`;
};

class Solution {
public:
    string simplifyPath(string& path) {
        path += '/';
        int k = 1, n = path.size();
        stack<int> st({1});
        for(int i = 1; i < n; ++i){
            if(path[i] == '/'){
                int prev = st.top();
                if(prev == k) continue;
                else if(path.substr(prev, k - prev) == ".") --k;
                else if(path.substr(prev, k - prev) == ".."){
                    if(st.size() > 1) st.pop();
                    k = st.top();
                }else {
                    path[k++] = path[i];
                    st.emplace(k);
                }
            }else path[k++] = path[i];
        }
        while(k > 1 && path[k - 1] == '/') --k;
        return path.substr(0, k);
    }
};

func simplifyPath(path string) string {
    ans := []string{}
    for _, v := range strings.Split(path, "/") {
        if v == ".." {
            if len(ans) > 0 {
                ans = ans[:len(ans)-1]
            }
        } else if v != "." && v != "" {
            ans = append(ans, v)
        }
    }

    return "/" + strings.Join(ans, "/")
}

class Solution:
    def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
        stack = []
        v = 0
        for num in pushed:
            stack.append(num)
            while  len(stack) > 0 and stack[-1] == popped[v] :
                stack.pop()
                v += 1

        return len(stack) == 0

function validateStackSequences(pushed: number[], popped: number[]): boolean {
    const l = pushed.length;
    const stack: number[] = []

    let c = 0;
    for (const p of pushed) {
        stack.push(p);
        while (stack.length && c < l && stack[stack.length - 1] == popped[c]) {
            stack.pop();
            c++;
        }
    }

    return c == l;
};

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Stack<Integer> stack = new Stack<>();
        int popIndex = 0;
        for (int i = 0; i < pushed.length; i++) {
            stack.push(pushed[i]);
            while (stack.size() > 0 && stack.peek() == popped[popIndex]) {       
               stack.pop();
               popIndex++;
            }
        }

        return stack.size() == 0;
    }
}

class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, const vector<int>& popped) {
        int k = -1, t = 0;
        for(int& e : pushed){
            pushed[++k] = e;
            while(k >= 0 && pushed[k] == popped[t])
                --k, ++t;
        }
        return k == -1;
    }
};

function validateStackSequences(pushed: number[], popped: number[]): boolean {
    const stack: number[] = [];

    let j = 0;
    for (const n of pushed) {
        stack.push(n);

        while (
            stack.length !== 0
            && j < pushed.length
            && stack.at(-1) === popped[j]
        ) {
            stack.pop();
            j++;
        }
    }

    return j === pushed.length;
};

class Solution:
    def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
        stack = []   
        while pushed or popped:
            if not stack:
                stack.append(pushed.pop(0))
            if stack[-1] != popped[0]:
                if not pushed: return False
                stack.append(pushed.pop(0))
            else:
                popped.pop(0)
                stack.pop()
        return True

class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        @lru_cache(None)
        def dp(i, j):
            if i == j:
                return 1
            if i > j:
                return 0
            if s[i] == s[j]:
                return 2 + dp(i+1, j-1)
            else:
                return max(dp(i+1, j), dp(i, j-1))
        
        return dp(0, len(s)-1)

function longestPalindromeSubseq(s: string): number {
    const r = s.split('').reverse().join('');
    const dp = Array.from({length: s.length + 1}, () => Array(r.length + 1).fill(0));
    for (let i = 1; i <= s.length; i++) {
        for (let j = 1; j <= r.length; j++) {
            if (s[i-1] === r[j-1]) {
                dp[i][j] = 1 + dp[i-1][j-1]
            } else {
                dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1])
            }
        }
    }
    return dp[s.length][r.length];
};

/**
 * @param {string} s
 * @return {number}
 */
var longestPalindromeSubseq = function(s) {
    const n = s.length;
    const arr = Array(n + 1).fill().map(() => Array(n).fill(0 + 1));
    for (let i = 0; i <= n; i++) {
        for (let j = 0; j <= n; j++) {
            if (!i || !j) {
                arr[i][j] = Math.max(i, j);
            } else {
                arr[i][j] = Math.min(
                    arr[i-1][j] + 1,
                    arr[i][j-1] + 1,
                    arr[i-1][j-1] + (s[i-1] === s[n-j] ? 0 : 2),
                );
            }
        }
    }

    return n - (arr[n][n] >> 1);
};

class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        @cache
        def f(l, r):
            if l > r:
                return 0
            if l == r:
                return 1
            
            if s[l] == s[r]:
                return f(l + 1, r - 1) + 2
            else:
                return max(f(l, r - 1), f(l + 1, r))
            
        return f(0, len(s) - 1)

class Solution {
public:
    vector <vector <int>> dp;
    int longestPalindromeSubseq(string s) {
        int len = s.length();
        dp.resize(len + 1, vector <int> (len + 1));
        s = ' ' + s;
        for (int i = 1; i <= len; ++ i) {
            dp[i][i] = 1;
        }
        for (int sz = 2; sz <= len; ++ sz) {
            for (int i = 1; i <= len - sz + 1; ++ i) {
                int j = i + sz - 1;
                dp[i][j] = max(dp[i][j - 1], dp[i + 1][j]);
                if (s[i] == s[j]) {
                    dp[i][j] = max(dp[i][j], dp[i + 1][j - 1] + 2);
                }
            }
        }
        return dp[1][len];
    }
};