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

class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        flips = 0
        length = (1 << n) - 1
        while k > 1:
            mid = length//2 + 1
            if k == mid:
                return str(1^flips)

            elif k > mid:
                k -= 2*(k - mid)
                flips ^= 1
           
            length//=2

        return str(flips^0)

class Solution:
    def parseBoolExpr(self, expression: str) -> bool:
        stack = []
        for char in expression:
            if not stack or char != ")":
                stack.append(char)
                continue

            countF = 0
            countT = 0
            while stack[-1] != '(':
                item = stack.pop()
                if item == 'f':
                    countF += 1
                elif item =='t':
                    countT += 1

            stack.pop()
            expression = ""
            if stack[-1] == '&':
                expression = 'f' if countF > 0 else 't'
            elif stack[-1] == '|':
                expression = 't' if countT > 0 else 'f'
            elif stack[-1] == '!':
                expression = 't' if countF == 1 else 'f'
            
            stack.pop()
            stack.append(expression)
        
        return True if stack[-1] == 't' else False

class Solution {
public:
    bool parseBoolExpr(string expression) {
        stack<char> exps;
        stack<char> values;
        for (char c : expression) {
            switch (c)
            {
            case '!':
            case '&':
            case '|':
                exps.push(c);
                break;
            case 't':
            case 'f':
            case '(':
                values.push(c);
                break;
            case ')':
                evaluates(exps, values);
                break;
            default:
                break;
            }
        }
        return values.top() == 't' ? true : false;
    }
    void evaluates(stack<char>& exps, stack<char>& values) {
        char ex = exps.top();
        exps.pop();
        char v = '\0';
        if (ex == '&')
            v = 't';
        else if (ex == '|')
            v = 'f';
        char top;
        do {
            top = values.top();
            values.pop();
            if (top == '(') break;
            switch (ex)
            {
            case '!':
                v = (top == 't') ? 'f' : 't';
                break;
            case '&':
                v = (v == 't' && 't' == top) ? 't' : 'f';
                break;
            case '|':
                v = (v == 't' || 't' == top) ? 't' : 'f';
                break;
            default:
                break;
            }
        } while (!values.empty());
        values.push(v);
    }
};

[CODE]
[SPOILER]

class Solution:
    def parseBoolExpr(self, expression: str) -> bool:
        stack = []
        def isOp(c):
            return c == '&' or c == '|' or c == '!'

        for c in expression:
            if isOp(c):
                stack.append(c)
            if c in 'tf':
                stack.append(True if c == 't' else False)
            if c == ')':
                values = []
                while stack:
                    next = stack.pop()
                    if isOp(next):
                        value = values[0]
                        if next == '!':
                            value = not value
                        elif next == '&':
                            value = reduce(lambda a, b: a and b, values)
                        else:
                            value = reduce(lambda a, b: a or b, values)
                        stack.append(value)
                        break
                    values.append(next)
        return stack[0]

class Solution {
    func parseBoolExpr(_ expression: String) -> Bool {
        var stack: [Character] = []
        for char in expression {
            if char == ")" {
                var hasTrue = false
                var hasFalse = false
                while let top = stack.popLast(), top != "(" {
                    if top == "t" {
                        hasTrue = true
                    } else {
                        hasFalse = true
                    }
                }
                //
                let oper = stack.removeLast()
                var newValue = false
                if oper == "!" {
                    newValue = hasFalse
                } else if oper == "&" {
                    newValue = !hasFalse
                } else {
                    newValue = hasTrue
                }
                stack.append(newValue ? "t" : "f")
            } else if char != "," {
                stack.append(char)
            }
        }
        return stack[0] == "t" // Should have only 1 char left
    }
}

public class Solution
{
    public bool ParseBoolExpr(string expression)
    {
        Stack<char> operators = new();
        Stack<char> operands = new();

        for (int i = 0; i < expression.Length; i++)
        {
            char c = expression[i];
            if (c == ',')
            {
                continue;
            }
            if (c == '(')
            {
                operands.Push(c);
                continue;
            }
            if (c == '&' || c == '|' || c == '!')
            {
                operators.Push(c);
                continue;
            }
            if (c == ')')
            {
                Calculate(operators, operands);
                continue;
            }
            
            operands.Push(c);
        }

        return operands.Pop() == 't';
    }

    private void Calculate(Stack<char> operators, Stack<char> operands)
    {
        char op = operators.Pop();
        List<char> values = new();

        while (operands.Count > 0)
        {
            char operand = operands.Pop();
            if (operand == '(')
            {
                break;
            }
            values.Add(operand);
        }

        if (op == '&')
        {
            operands.Push(And(values) ? 't' : 'f');
        }
        else if (op == '|')
        {
            operands.Push(Or(values) ? 't' : 'f');
        }
        else if (op == '!')
        {
            operands.Push(Not(values[0]) ? 't' : 'f');
        }
    }

    private bool And(List<char> operands)
    {
        foreach (char operand in operands)
        {
            if (operand == 'f')
            {
                return false;
            }
        }
        return true;
    }

    private bool Or(List<char> operands)
    {
        foreach (char operand in operands)
        {
            if (operand == 't')
            {
                return true;
            }
        }
        return false;
    }

    private bool Not(char operand)
    {
        return operand == 'f';
    }
}

class Solution {
    public boolean parseBoolExpr(String expression) {
        int n = expression.length();
        if (n == 1)
            return expression.equals("t") ? true : false;
        boolean res = false;
        Stack<Boolean> stack = new Stack<>();
        int r = n - 1;
        char c = 't';
        for(int i  =1 ; i < n;i++){
            c = expression.charAt(i);
            if(c==',' || c=='(' ||c==')') continue;
            if(c=='!' || c=='&' || c=='|'){
                r= i+2;
                int open=1;
                while(open!=0){
                    char cr = expression.charAt(r);
                    if(cr=='(') open++;
                    else if(cr==')') open--;
                    r++;
                }
            }
            else{
                r=i+1;
            }
            stack.push(parseBoolExpr(expression.substring(i,r)));
            i=r;
        }
        res = stack.pop();
        c = expression.charAt(0);
        if (c == '|') {
            while (!stack.isEmpty()) {
                res |= stack.pop();
            }
        } else if (c == '&') {
            while (!stack.isEmpty()) {
                res &= stack.pop();
            }
        } else if (c == '!') {
            res = !res;
        }
        return res;
    }
}

public bool ParseBoolExpr(string expression)
{
    switch (expression)
    {
        case "f":
            return false;
        case "t":
            return true;
    }

    var operatorChar = expression.First();
    var remainExpression = expression.Substring(1, expression.Length - 1);
    if (remainExpression.First() == '(' && remainExpression.Last() == ')')
    {
        remainExpression = remainExpression.Substring(1, remainExpression.Length - 2);
    }
    if (operatorChar == '!')
    {
        return !ParseBoolExpr(remainExpression);
    }

    var childExpressions = SplitExpression(remainExpression);

    var res = ParseBoolExpr(childExpressions[0]);
    for (int i = 1; i < childExpressions.Length; i++)
    {
        if (operatorChar == '&')
        {
            res = res && ParseBoolExpr(childExpressions[i]);
        }
        else
        {
            res = res || ParseBoolExpr(childExpressions[i]);
        }
    }

    return res;
}

private string[] SplitExpression(string str)
{
    var res = new List<string>();
    var cntOpen = 0;
    var start = 0;

    for(int i = 0; i < str.Length; i ++)
    {
        switch (str[i])
        {
            case '(':
                cntOpen++;
                break;
            case ')':
                cntOpen--;
                break;
            case ',':
                continue;
            case '&':
                continue;
            case '!':
                continue;
            case '|':
                continue;
        }

        if (cntOpen == 0)
        {
            res.Add(str.Substring(start, i - start + 1));
            start = i + 2;
        }
    }

    return res.ToArray();
}

class Solution:
    def parseBoolExpr(self, expression: str) -> bool:
        opStack = []
        strToBool = {'t': True, 'f': False}
        boolToString = {True: 't', False: 'f'}

        for i in range(len(expression)):
            if expression[i] in ('&', '|', '!', 't', 'f'):
                opStack.append(expression[i])
            if expression[i] == ')':
                currBools = []
                while opStack[-1] in ('t', 'f'):
                    currBools.append(opStack.pop())
               
                op = opStack.pop()

                tmp = strToBool[currBools[0]]
                for b in currBools:
                    if op == '&':
                        tmp = tmp and strToBool[b]
                    if op == '!':
                        tmp = not strToBool[b]
                    if op == '|':
                        tmp = tmp or strToBool[b]

                opStack.append(boolToString[tmp])

        return strToBool[opStack[0]]

class Solution {
    public boolean parseBoolExpr(String expression) {
        Stack<Character> stack = new Stack<>();
        for (char c : expression.toCharArray()) {
            if (c == ')') {
                ArrayList<Character> values = new ArrayList<>();
                while (stack.peek() != '(') {
                    values.add(stack.pop());
                }
                stack.pop();
                char op = stack.pop();
                char result = evaluateSubExpr(op, values);
                stack.push(result);
            } else if (c != ',') {
                stack.push(c);
            }
        }
        return stack.peek() == 't';
    }

    private char evaluateSubExpr(char op, ArrayList<Character> values) {
        if (op == '!') return values.get(0) == 't' ? 'f' : 't';
        if (op == '&') {
            for (char value : values) {
                if (value == 'f') return 'f';
            }
            return 't';
        }
        if (op == '|') {
            for (char value : values) {
                if (value == 't') return 't';
            }
            return 'f';
        }
        return 'f';
    }
}

operatorMap = {
    '!': lambda a: not a,
    '&': lambda a, b: a and b,
    '|': lambda a, b: a or b
}
unaryOperators = ['!'] 
operatorNeutralVal = {
    '&': True,
    '|': False
}

class Solution:
    def parseBoolExpr(self, expression: str) -> bool:
        def evaluate(i):
            operatorChar = expression[i]
            operator = operatorMap[operatorChar]
            currentVal = operatorNeutralVal.get(operatorChar, None)
            i += 1
            while expression[i] != ')':
                char = expression[i]
                if char in '(,':
                    i += 1
                    continue
                if char in operatorMap:
                    nextVal, i = evaluate(i)
                else:
                    nextVal = char == 't'
                    i += 1

                if operatorChar in unaryOperators:
                    currentVal = operator(nextVal)
                    break
                currentVal = operator(currentVal, nextVal)
                
            return currentVal, i + 1
        
        return evaluate(0)[0]

class Solution:
    def eval(vals: list[bool], op: str) -> bool:
        if op == '|':
            return any(vals)
        elif op == '&':
            return all(vals)
        elif op == '!':
            return not vals[0]

    def parseBoolExpr(self, expression: str) -> bool:
        stack = []
        vals = []
        for c in expression:
            if c == ')':
                vals = []
                while stack[-1] != '(':
                    vals.append(stack.pop())
                stack.pop() # remove '('
                op = stack.pop()
                stack.append(Solution.eval(vals, op))
            elif c != ',':
                if c == 't':
                    stack.append(True)
                elif c == 'f':
                    stack.append(False)
                else:
                    stack.append(c)
        return stack[0]

if __name__ == '__main__':
    s = Solution()
    expression = "|(&(t,f,t),t)"
    print(s.parseBoolExpr(expression))

class Solution {
public:
    int maxUniqueSplit(string s) {
        unordered_set<string> set;
        int ans = 0;
        backtrack(s, 0, set, ans, 0);
        return ans;
    }
    void backtrack(string &s, int index, unordered_set<string> &set, int &ans, int count) {
        if (index == s.size()) ans = max(ans, count);
        for (int i = index; i < s.size(); i++) {
            string sub = s.substr(index, i - index + 1);
            if (set.find(sub) != set.end()) continue;
            set.insert(sub);
            backtrack(s, i + 1, set, ans, count + 1);
            set.erase(sub);
        }
    }
};

class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        subStrings = []
        self.result = 0
        def backtrack(i):
            if i == len(s):
                if len(subStrings) == len(set(subStrings)):
                    self.result = max(self.result, len(subStrings))
                return
            
            subStrings.append(s[i])
            backtrack(i+1)
            subStrings.pop()
            
            if len(subStrings) > 0:
                subStrings[-1] = subStrings[-1] + s[i]
                backtrack(i+1)
                subStrings[-1] = subStrings[-1][:-1]
        backtrack(0)
        return self.result

class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        strings = set()
        n = len(s)
        def backtrack(i):
            if i == n:
                return 0
            maxCount = 0
            current = ""
            for j in range(i, n):
                current += s[j]
                if current not in strings:
                    strings.add(current)
                    maxCount = max(maxCount, 1 + backtrack(j + 1))
                    strings.remove(current)
            return maxCount
        return backtrack(0)

function maxUniqueSplit(s: string): number {
    const set = new Set();
    const go = (l: number)  => {
        if (l === s.length) return 0;
        let res = 0;
        for (let r = l + 1; r <= s.length; r++) {
            const str = s.substring(l, r);
            if (!set.has(str)) {
                set.add(str);
                res = Math.max(res, 1 + go(r));
                set.delete(str)
            }
        }
        return res
    }
    return go(0)
};