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

class Solution:
    def findRotateSteps(self, ring: str, key: str) -> int:
        ring_length = len(ring)
   
        dp = [float("inf")] * ring_length
        dp[0] = 0
   
        prev_char = ""
   
        for char in key:
            if char == prev_char:
                dp = [x + 1 for x in dp]
            else:
                new_dp = [float("inf")] * ring_length
                for pos in range (ring_length):
                    if ring[pos] == char:
                        new_dp[pos] = min([1 + dp[i] + min((i-pos) % ring_length,(pos-i) % ring_length) for i in range (ring_length)])
                dp = new_dp
                prev_char = char

        return min(dp)

from collections import defaultdict
class Solution:
    def findRotateSteps(self, ring: str, key: str) -> int:
        hashChar = defaultdict(list)
        size = len(ring)
        for idx, char in enumerate(ring):
            hashChar[char].append(idx)
        cur = ring[0]
        dp = [0]
        for char in key:
            if cur == char:
                continue
            charIdxs = hashChar[char]
            nextDp = []
            for charIdx in charIdxs:
                minUntil = 101 * 101
                for idx, value in enumerate(dp):
                    step = min((hashChar[cur][idx] - charIdx) % size, (charIdx-hashChar[cur][idx]) % size)
                    minUntil = min(minUntil, step + value)
                nextDp.append(minUntil)                 
            cur = char
            dp = nextDp
        return min(dp) + len(key)

public int FindRotateSteps(string ring, string key)
    {
        int n = ring.Length;
        int m = key.Length;
        int[][] dp = new int[m + 1][];
        for(int i = 0; i <= m; i++)
            dp[i] = new int[n];
        
        for(int i = m - 1; i >= 0; i--)
            for(int j = 0; j < n; j++)
            {
                dp[i][j] = int.MaxValue;
                for(int k = 0; k < n; k++)
                    if(ring[k] == key[i])
                    {
                        int diff = Math.Abs(j - k);
                        int step = Math.Min(diff, n - diff);
                        dp[i][j] = Math.Min(dp[i][j], step + dp[i + 1][k]);
                    }
            }
        return dp[0][0] + m;
    }

class Solution
{
public:
    int n;
    int m;
    unordered_map<char, vector<int>> idx;
    string key;
    vector<vector<int>> dp;
    int calcDis(int a, int b){
        int mi = min(a, b);
        int ma = max(a, b);
        return min(ma - mi, mi + n - ma);
    }
    int solve(int currRingIdx, int currKeyIdx){
        if(currKeyIdx >= m){
            return 0;
        }

        if(dp[currRingIdx][currKeyIdx] != -1){
            return dp[currRingIdx][currKeyIdx];
        }

        int ans = INT_MAX;
        for(auto i: idx[key[currKeyIdx]]){
            ans = min(ans, calcDis(i, currRingIdx) + 1 + solve(i, currKeyIdx + 1));
        }

        return dp[currRingIdx][currKeyIdx] = ans;
    }
    int findRotateSteps(string ring, string key)
    {
        n = ring.size();
        m = key.size();
        this->key = key;
        idx.clear();
        for(int i = 0; i < n;i +=1){
            idx[ring[i]].emplace_back(i);
        }
        dp = vector<vector<int>>(n, vector<int>(m, -1));
        return solve(0, 0);
    }
};

var findRotateSteps = function(ring, key) {
    const memo = [], n = ring.length;
    const go = (i, j) => {
        if (j === key.length) {
            return 0;
        }
        memo[i] ??= [];
        if (memo[i][j] !== undefined) {
            return memo[i][j];
        }
        let result = +Infinity;
        const ch = key[j];
        for (let ii = i; ii < i + n; ii++) {
            const iii = ii % n;
            if (ring[iii] !== ch) {
                continue;
            }
            result = Math.min(
                result,
                Math.min(Math.abs(i - iii), n - Math.abs(i - iii)) + 1 + go(iii, j + 1)
            );
        }
        return memo[i][j] = result;
    };
    return go(0, 0);
};

class Solution:
    def findRotateSteps(self, ring: str, key: str) -> int:
        m, n = len(ring), len(key)

        def count_steps(curr, next):
            return min(abs(curr - next), m - abs(curr - next))

        @lru_cache(None)
        def dfs(idr, idk):
            if idk == len(key):
                return 0
            steps = 10 ** 9 + 7
            for i in range(m):
                if ring[i] == key[idk]:
                    steps = min(steps, count_steps(idr, i) + 1 + dfs(i, idk + 1))
            
            return steps

use std::cmp;
use std::collections::HashMap;
impl Solution {
    pub fn find_rotate_steps(ring: String, key: String) -> i32 {
        let ring_bytes = ring.as_bytes();
        let key_bytes = key.as_bytes();
        let ring_length = ring_bytes.len();
        let key_length = key_bytes.len();
        let mut ring_char_to_index_map = HashMap::<u8, Vec<usize>>::new();
        for (ring_index, &ring_char) in ring_bytes.iter().enumerate() {
            if let Some(indices) = ring_char_to_index_map.get_mut(&ring_char) {
                indices.push(ring_index);
            } else {
                ring_char_to_index_map.insert(ring_char, vec![ring_index]);
            }
        }
        let mut dp = vec![vec![usize::MAX; ring_length]; key_length + 1];
        for ring_index in 0..ring_length {
            dp[key_length][ring_index] = 0;
        }
        for target_key_index in (0..key_length).into_iter().rev() {
            let target_key_char = key_bytes[target_key_index];
            for source_ring_index in 0..ring_length {
                for &target_ring_index in ring_char_to_index_map.get(&target_key_char).unwrap().iter() {
                    let distance = Self::distance(source_ring_index, target_ring_index, ring_length);
                    let remaining_cost = dp[target_key_index + 1][target_ring_index];
                    let old_estimate = dp[target_key_index][source_ring_index];
                    dp[target_key_index][source_ring_index] = cmp::min(old_estimate, distance + remaining_cost + 1);
                }
            }
        }
        dp[0][0] as i32
    }
    fn distance(a: usize, b: usize, ring_length: usize) -> usize {
        let max = cmp::max(a, b);
        let min = cmp::min(a, b);
        cmp::min(max - min, (ring_length - max) + min)
    }
}
}

from collections import defaultdict
class Solution:
    def sumOfDistancesInTree(self, n: int, edges: List[List[int]]) -> List[int]:
        self.count = {}
        self.distance = {}
        edgeMap = defaultdict(list)
        for edge in edges:
            edgeMap[edge[0]].append(edge[1])
            edgeMap[edge[1]].append(edge[0])
        def dfs(node: int, edgeMap, parent, step):
            self.distance[node] = step
            count = 1
            for neighbour in edgeMap.get(node, []):
                if neighbour != parent:
                    count += dfs(neighbour, edgeMap, node, step+1)
            self.count[node] = count
            return count
        dfs(0, edgeMap, -1, 0)
        result = [0 for i in range(n)]
        result[0] = sum(self.distance.values())
        def calRes(node: int, edgeMap, parent, n):
            result[node] = result[parent] + n - 2*self.count[node]
            for neighbour in edgeMap.get(node, []):
                if neighbour != parent:
                     calRes(neighbour, edgeMap, node, n)
        for neighour in edgeMap.get(0, []):
            calRes(neighour, edgeMap, 0, n)
        return result

/**
 * @param {number} n
 * @param {number[][]} edges
 * @return {number[]}
 */
var sumOfDistancesInTree = function(n, edges) {
    const nb = {},
        sizes = [],
        add = Array.from({ length: n }).fill(0),
        ans = [];
    edges.forEach(([u, v]) => {
        nb[u] ||= [];
        nb[u].push(v);
        nb[v] ||= [];
        nb[v].push(u);
    });
    const calcSize = (node, parent) => {
        sizes[node] = 1;
        (nb[node] || []).forEach(child => {
            if (child !== parent) {
                sizes[node] += calcSize(child, node);
            }
        });
        return sizes[node];
    };
    calcSize(0, -1);
    const traversal = (node, parent) => {
        (nb[node] || []).forEach(child => {
            if (child !== parent) {
                add[0] += sizes[child];
                add[child] -= sizes[child];
                add[child] += n - sizes[child];
                traversal(child, node);
            }
        });
    };
    traversal(0, -1);
    // console.log(add); return [];
    const flatten = (node, parent, _add) => {
        ans[node] = add[node] + _add;
        (nb[node] || []).forEach(child => {
            if (child !== parent) {
                flatten(child, node, _add + add[node]);
            }
        });
    };
    flatten(0, -1, 0);
    return ans;
}