10:I[13699,["/_next/static/chunks/6b91a202b724e571.js","/_next/static/chunks/6710f67d945945a1.js","/_next/static/chunks/cb0f98aea04386f6.js"],"default"] 11:I[25152,["/_next/static/chunks/6b91a202b724e571.js","/_next/static/chunks/6710f67d945945a1.js","/_next/static/chunks/cb0f98aea04386f6.js"],"default"] 12:T486,class Solution: def minimumDistance(self, word: str) -> int: n = len(word) BIG = 2**30 dp = [[[BIG] * 26 for x in range(26)] for y in range(n)] for i in range(26): dp[0][i][ord(word[0]) - 65] = 0 dp[0][ord(word[0]) - 65][i] = 0 def getDistance(p, q): x1, y1 = p // 6, p % 6 x2, y2 = q // 6, q % 6 return abs(x1 - x2) + abs(y1 - y2) for i in range(1, n): cur, prev = ord(word[i]) - 65, ord(word[i - 1]) - 65 d = getDistance(prev, cur) for j in range(26): dp[i][cur][j] = min(dp[i][cur][j], dp[i - 1][prev][j] + d) dp[i][j][cur] = min(dp[i][j][cur], dp[i - 1][j][prev] + d) if prev == j: for k in range(26): d0 = getDistance(k, cur) dp[i][cur][j] = min(dp[i][cur][j], dp[i - 1][k][j] + d0) dp[i][j][cur] = min(dp[i][j][cur], dp[i - 1][j][k] + d0) ans = min(min(dp[n - 1][x]) for x in range(26)) return ans13:T44d,class Solution { public int minimumDistance(String word) { int n = word.length(); int[][] dp = new int[n][26]; for (int i = 1; i < n; i++) { Arrays.fill(dp[i], 1000000000); } for (int i = 1; i < n; i++) { int cur = word.charAt(i) - 'A'; int prev = word.charAt(i - 1) - 'A'; int d = getDistance(prev, cur); for (int j = 0; j < 26; j++) { dp[i][j] = Math.min(dp[i][j], dp[i - 1][j] + d); if (prev == j) { for (int k = 0; k < 26; k++) { int d0 = getDistance(k, cur); dp[i][j] = Math.min(dp[i][j], dp[i - 1][k] + d0); } } } } int ans = Integer.MAX_VALUE; for (int x : dp[n - 1]) ans = Math.min(ans, x); return ans; } private int getDistance(int p, int q) { int x1 = p / 6, y1 = p % 6; int x2 = q / 6, y2 = q % 6; return Math.abs(x1 - x2) + Math.abs(y1 - y2); } }14:T41c,class Solution { public: int minimumDistance(string word) { int n = word.length(); vector> dp(n, vector(26, 1e9)); for (int i = 0; i < 26; i++) dp[0][i] = 0; auto getDistance = [](int p, int q) { int x1 = p / 6, y1 = p % 6; int x2 = q / 6, y2 = q % 6; return abs(x1 - x2) + abs(y1 - y2); }; for (int i = 1; i < n; i++) { int cur = word[i] - 'A'; int prev = word[i - 1] - 'A'; int d = getDistance(prev, cur); for (int j = 0; j < 26; j++) { dp[i][j] = min(dp[i][j], dp[i - 1][j] + d); if (prev == j) { for (int k = 0; k < 26; k++) { int d0 = getDistance(k, cur); dp[i][j] = min(dp[i][j], dp[i - 1][k] + d0); } } } } int ans = 1e9; for (int x : dp[n - 1]) ans = min(ans, x); return ans; } };

Time Complexity

Space Complexity