方法一：动态规划
我们用 dp[i][l][r] 表示在输入了字符串 word 的第 i 个字母后，左手的位置为 l，右手的位置为 r，达到该状态的最小移动距离。这里的位置为指向的字母编号，例如 A 对应 0，B 对应 1，以此类推，而非字母在键盘上的位置。这样做的好处是将字母的位置映射成一个整数而非二维的坐标，使得我们更加方便地进行状态转移。
那么如何进行状态转移呢？我们首先需要看出一个非常重要的性质：对于状态 dp[i][l][r]，要么 word[i] == l，要么 word[i] == r，即在输入了第 i 个字母后，左手和右手中至少有一个在 word[i] 的位置。我们可以根据这两种情况，分别进行状态转移：
对于每一个状态 dp[i][l][r]，我们取它所有转移中的最小值，即为输入了字符串 word 的第 i 个字母后，左手的位置为 l，右手的位置为 r，达到该状态的最小移动距离。
在这个动态规划中，我们还需要考虑不合法的状态以及边界状态。对于某一个不合法的状态，如果用它来进行状态转移，可能会使得 dp[i][l][r] 取到一个更小且不合法的值。因此，我们一般会给所有不合法的状态赋予一个非常大的值（例如 C++ 中的整数最大值 INT_MAX），这样即使用它来进行状态转移，也会因为本身值非常大的缘故，对最优解没有任何影响。在考虑边界状态时，由于题目中规定两根手指的起始位置是零代价的，因此对于字符串中的第 0 个字母 word[0]，输入它的最小移动距离为 0。此时要么左手的位置为 word[0]，要么右手的位置为 word[0]，因此我们可以将所有的 dp[0][l = word[0]][r] 以及 dp[0][l][r = word[0]] 作为边界状态，它们的值为 0。
###C++
class Solution {
public:
int 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);
}
int minimumDistance(string word) {
int n = word.size();
int dp[n][26][26];
for (int i = 0; i < n; ++i) {
for (int j = 0; j < 26; ++j) {
fill(dp[i][j], dp[i][j] + 26, INT_MAX >> 1);
}
}
for (int i = 0; i < 26; ++i) {
dp[0][i][word[0] - 'A'] = dp[0][word[0] - 'A'][i] = 0;
}
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][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 (int k = 0; k < 26; ++k) {
int 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);
}
}
}
}
int ans = INT_MAX >> 1;
for (int i = 0; i < 26; ++i) {
for (int j = 0; j < 26; ++j) {
ans = min(ans, dp[n - 1][i][j]);
}
}
return ans;
}
};
###Python
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 ans
###Java
class Solution {
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);
}
public int minimumDistance(String word) {
int n = word.length();
int[][][] dp = new int[n][26][26];
for (int i = 0; i < n; ++i) {
for (int j = 0; j < 26; ++j) {
for (int k = 0; k < 26; ++k) {
dp[i][j][k] = Integer.MAX_VALUE / 2;
}
}
}
for (int i = 0; i < 26; ++i) {
dp[0][i][word.charAt(0) - 'A'] = 0;
dp[0][word.charAt(0) - 'A'][i] = 0;
}
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][cur][j] = Math.min(dp[i][cur][j], dp[i - 1][prev][j] + d);
dp[i][j][cur] = Math.min(dp[i][j][cur], dp[i - 1][j][prev] + d);
if (prev == j) {
for (int k = 0; k < 26; ++k) {
int d0 = getDistance(k, cur);
dp[i][cur][j] = Math.min(dp[i][cur][j], dp[i - 1][k][j] + d0);
dp[i][j][cur] = Math.min(dp[i][j][cur], dp[i - 1][j][k] + d0);
}
}
}
}
int ans = Integer.MAX_VALUE / 2;
for (int i = 0; i < 26; ++i) {
for (int j = 0; j < 26; ++j) {
ans = Math.min(ans, dp[n - 1][i][j]);
}
}
return ans;
}
}
###C#
public class Solution {
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);
}
public int MinimumDistance(string word) {
int n = word.Length;
int[,,] dp = new int[n, 26, 26];
for (int i = 0; i < n; ++i) {
for (int j = 0; j < 26; ++j) {
for (int k = 0; k < 26; ++k) {
dp[i, j, k] = int.MaxValue / 2;
}
}
}
for (int i = 0; i < 26; ++i) {
dp[0, i, word[0] - 'A'] = 0;
dp[0, word[0] - 'A', i] = 0;
}
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, cur, j] = Math.Min(dp[i, cur, j], dp[i - 1, prev, j] + d);
dp[i, j, cur] = Math.Min(dp[i, j, cur], dp[i - 1, j, prev] + d);
if (prev == j) {
for (int k = 0; k < 26; ++k) {
int d0 = GetDistance(k, cur);
dp[i, cur, j] = Math.Min(dp[i, cur, j], dp[i - 1, k, j] + d0);
dp[i, j, cur] = Math.Min(dp[i, j, cur], dp[i - 1, j, k] + d0);
}
}
}
}
int ans = int.MaxValue / 2;
for (int i = 0; i < 26; ++i) {
for (int j = 0; j < 26; ++j) {
ans = Math.Min(ans, dp[n - 1, i, j]);
}
}
return ans;
}
}
###Go
func getDistance(p, q int) int {
x1, y1 := p/6, p%6
x2, y2 := q/6, q%6
return abs(x1 - x2) + abs(y1 - y2)
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}
func minimumDistance(word string) int {
n := len(word)
dp := make([][26][26]int, n)
for i := 0; i < n; i++ {
for j := 0; j < 26; j++ {
for k := 0; k < 26; k++ {
dp[i][j][k] = 1 << 30
}
}
}
firstChar := int(word[0] - 'A')
for i := 0; i < 26; i++ {
dp[0][i][firstChar] = 0
dp[0][firstChar][i] = 0
}
for i := 1; i < n; i++ {
cur := int(word[i] - 'A')
prev := int(word[i-1] - 'A')
d := getDistance(prev, cur)
for j := 0; j < 26; j++ {
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 := 0; k < 26; k++ {
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 := 1 << 30
for i := 0; i < 26; i++ {
for j := 0; j < 26; j++ {
ans = min(ans, dp[n-1][i][j])
}
}
return ans
}
###C
int 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);
}
int minimumDistance(char* word) {
int n = strlen(word);
int*** dp = (int***)malloc(n * sizeof(int**));
for (int i = 0; i < n; ++i) {
dp[i] = (int**)malloc(26 * sizeof(int*));
for (int j = 0; j < 26; ++j) {
dp[i][j] = (int*)malloc(26 * sizeof(int));
for (int k = 0; k < 26; ++k) {
dp[i][j][k] = INT_MAX / 2;
}
}
}
for (int i = 0; i < 26; ++i) {
dp[0][i][word[0] - 'A'] = 0;
dp[0][word[0] - 'A'][i] = 0;
}
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][cur][j] = fmin(dp[i][cur][j], dp[i - 1][prev][j] + d);
dp[i][j][cur] = fmin(dp[i][j][cur], dp[i - 1][j][prev] + d);
if (prev == j) {
for (int k = 0; k < 26; ++k) {
int d0 = getDistance(k, cur);
dp[i][cur][j] = fmin(dp[i][cur][j], dp[i - 1][k][j] + d0);
dp[i][j][cur] = fmin(dp[i][j][cur], dp[i - 1][j][k] + d0);
}
}
}
}
int ans = INT_MAX / 2;
for (int i = 0; i < 26; ++i) {
for (int j = 0; j < 26; ++j) {
if (ans > dp[n - 1][i][j]) {
ans = dp[n - 1][i][j];
}
}
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < 26; ++j) {
free(dp[i][j]);
}
free(dp[i]);
}
free(dp);
return ans;
}
###JavaScript
var minimumDistance = function(word) {
const n = word.length;
const getDistance = (p, q) => {
const x1 = Math.floor(p / 6), y1 = p % 6;
const x2 = Math.floor(q / 6), y2 = q % 6;
return Math.abs(x1 - x2) + Math.abs(y1 - y2);
};
const dp = new Array(n);
for (let i = 0; i < n; i++) {
dp[i] = new Array(26);
for (let j = 0; j < 26; j++) {
dp[i][j] = new Array(26).fill(Math.floor(Number.MAX_SAFE_INTEGER / 2));
}
}
const firstChar = word.charCodeAt(0) - 65;
for (let i = 0; i < 26; i++) {
dp[0][i][firstChar] = 0;
dp[0][firstChar][i] = 0;
}
for (let i = 1; i < n; i++) {
const cur = word.charCodeAt(i) - 65;
const prev = word.charCodeAt(i - 1) - 65;
const d = getDistance(prev, cur);
for (let j = 0; j < 26; j++) {
dp[i][cur][j] = Math.min(dp[i][cur][j], dp[i - 1][prev][j] + d);
dp[i][j][cur] = Math.min(dp[i][j][cur], dp[i - 1][j][prev] + d);
if (prev === j) {
for (let k = 0; k < 26; k++) {
const d0 = getDistance(k, cur);
dp[i][cur][j] = Math.min(dp[i][cur][j], dp[i - 1][k][j] + d0);
dp[i][j][cur] = Math.min(dp[i][j][cur], dp[i - 1][j][k] + d0);
}
}
}
}
let ans = Number.MAX_SAFE_INTEGER;
for (let i = 0; i < 26; i++) {
for (let j = 0; j < 26; j++) {
ans = Math.min(ans, dp[n - 1][i][j]);
}
}
return ans;
};
###TypeScript
function minimumDistance(word: string): number {
const n = word.length;
const getDistance = (p: number, q: number): number => {
const x1 = Math.floor(p / 6), y1 = p % 6;
const x2 = Math.floor(q / 6), y2 = q % 6;
return Math.abs(x1 - x2) + Math.abs(y1 - y2);
};
const dp: number[][][] = new Array(n);
for (let i = 0; i < n; i++) {
dp[i] = new Array(26);
for (let j = 0; j < 26; j++) {
dp[i][j] = new Array(26).fill(Math.floor(Number.MAX_SAFE_INTEGER / 2));
}
}
const firstChar = word.charCodeAt(0) - 65;
for (let i = 0; i < 26; i++) {
dp[0][i][firstChar] = 0;
dp[0][firstChar][i] = 0;
}
for (let i = 1; i < n; i++) {
const cur = word.charCodeAt(i) - 65;
const prev = word.charCodeAt(i - 1) - 65;
const d = getDistance(prev, cur);
for (let j = 0; j < 26; j++) {
dp[i][cur][j] = Math.min(dp[i][cur][j], dp[i - 1][prev][j] + d);
dp[i][j][cur] = Math.min(dp[i][j][cur], dp[i - 1][j][prev] + d);
if (prev === j) {
for (let k = 0; k < 26; k++) {
const d0 = getDistance(k, cur);
dp[i][cur][j] = Math.min(dp[i][cur][j], dp[i - 1][k][j] + d0);
dp[i][j][cur] = Math.min(dp[i][j][cur], dp[i - 1][j][k] + d0);
}
}
}
}
let ans = Number.MAX_SAFE_INTEGER;
for (let i = 0; i < 26; i++) {
for (let j = 0; j < 26; j++) {
ans = Math.min(ans, dp[n - 1][i][j]);
}
}
return ans;
}
###Rust
impl Solution {
fn get_distance(p: i32, q: i32) -> i32 {
let x1 = p / 6;
let y1 = p % 6;
let x2 = q / 6;
let y2 = q % 6;
(x1 - x2).abs() + (y1 - y2).abs()
}
pub fn minimum_distance(word: String) -> i32 {
let n = word.len();
let word_chars: Vec<char> = word.chars().collect();
let mut dp = vec![vec![vec![i32::MAX >> 1; 26]; 26]; n];
let first_char = (word_chars[0] as u8 - b'A') as usize;
for i in 0..26 {
dp[0][i][first_char] = 0;
dp[0][first_char][i] = 0;
}
for i in 1..n {
let cur = (word_chars[i] as u8 - b'A') as i32;
let prev = (word_chars[i - 1] as u8 - b'A') as i32;
let d = Self::get_distance(prev, cur);
for j in 0..26 {
let j_i32 = j as i32;
dp[i][cur as usize][j] = dp[i][cur as usize][j].min(
dp[i - 1][prev as usize][j].saturating_add(d)
);
dp[i][j][cur as usize] = dp[i][j][cur as usize].min(
dp[i - 1][j][prev as usize].saturating_add(d)
);
if prev == j_i32 {
for k in 0..26 {
let d0 = Self::get_distance(k as i32, cur);
dp[i][cur as usize][j] = dp[i][cur as usize][j].min(
dp[i - 1][k][j].saturating_add(d0)
);
dp[i][j][cur as usize] = dp[i][j][cur as usize].min(
dp[i - 1][j][k].saturating_add(d0)
);
}
}
}
}
let mut ans = i32::MAX >> 1;
for i in 0..26 {
for j in 0..26 {
ans = ans.min(dp[n - 1][i][j]);
}
}
ans
}
}
复杂度分析
-
时间复杂度：$O(|\Sigma|N)$，其中 $N$ 是字符串 word 的长度，$|\Sigma|$ 是可能出现的字母数量，在本题中 $|\Sigma| = 26$。对于状态 dp[i][l][r]，枚举 i 需要的时间复杂度为 $O(N)$，在此之后，如果 word[i] == l，根据上面的状态转移方程：
如果 word[i] == r，分析的过程相同，在此不再赘述。这样总时间复杂度即为 $O(|\Sigma|N)$。
-
空间复杂度：$O(|\Sigma|^2 N)$。
方法二：动态规划 + 空间优化
在方法一中，我们提到了一条重要的性质：对于状态 dp[i][l][r]，要么 word[i] == l，要么 word[i] == r，即在输入了第 i 个字母后，左手和右手中至少有一个在 word[i] 的位置。那么对于每一个 i，我们其实只需要存储 $2|\Sigma|$ 而不是 $|\Sigma|^2$ 个状态。例如我们可以用 dp[i][op][rest] 表示状态，其中 op 的值只能为 0 或 1，op == 0 表示左手在 word[i] 的位置，op == 1 表示右手在 word[i] 的位置，而 rest 表示不在 word[i] 位置的另一只手的位置。这样我们在状态转移方程几乎不变的前提下，减少了动态规划需要的空间。
那么我们是否还可以继续进行优化呢？我们可以发现，在方法一中，状态转移方程具有高度对称性，那么我们可以断定，dp[i][op = 0][rest] 和 dp[i][op = 1][rest] 的值一定是相等的。这是因为 dp[i][op = 0][rest] 表示左手在 word[i] 的位置且右手在 rest 的位置，如果我们将左右手互换，那么我们同样可以使用 dp[i][op = 0][rest] 的移动距离使得右手在 word[i] 的位置且左手在 rest 的位置，而这恰好就是 dp[i][op = 1][rest]。
因此我们可以直接使用 dp[i][rest] 进行状态转移，其表示一只手在 word[i] 的位置，另一只手在 rest 的位置的最小移动距离。我们并不需要关心具体哪只手在 word[i] 的位置，因为两只手是完全对称的。这样以来，我们将三维的动态规划优化至了二维，大大减少了空间的使用。
###C++
class Solution {
public:
int 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);
}
int minimumDistance(string word) {
int n = word.size();
vector<vector<int>> dp(n, vector<int>(26, INT_MAX >> 1));
fill(dp[0].begin(), dp[0].end(), 0);
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 = *min_element(dp[n - 1].begin(), dp[n - 1].end());
return ans;
}
};
###Python
class Solution:
def minimumDistance(self, word: str) -> int:
n = len(word)
BIG = 2**30
dp = [[0] * 26] + [[BIG] * 26 for _ in range(n - 1)]
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][j] = min(dp[i][j], dp[i - 1][j] + d)
if prev == j:
for k in range(26):
d0 = getDistance(k, cur)
dp[i][j] = min(dp[i][j], dp[i - 1][k] + d0)
ans = min(dp[n - 1])
return ans
###Java
class Solution {
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);
}
public int minimumDistance(String word) {
int n = word.length();
int[][] dp = new int[n][26];
for (int i = 0; i < n; i++) {
Arrays.fill(dp[i], Integer.MAX_VALUE / 2);
}
Arrays.fill(dp[0], 0);
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 / 2;
for (int value : dp[n - 1]) {
ans = Math.min(ans, value);
}
return ans;
}
}
###C#
public class Solution {
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);
}
public int MinimumDistance(string word) {
int n = word.Length;
int[,] dp = new int[n, 26];
for (int i = 0; i < n; i++) {
for (int j = 0; j < 26; j++) {
dp[i, j] = int.MaxValue / 2;
}
}
for (int j = 0; j < 26; j++) {
dp[0, j] = 0;
}
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] = 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 = int.MaxValue / 2;
for (int j = 0; j < 26; j++) {
ans = Math.Min(ans, dp[n - 1, j]);
}
return ans;
}
}
###Go
func getDistance(p, q int) int {
x1, y1 := p / 6, p % 6
x2, y2 := q / 6, q % 6
return abs(x1 - x2) + abs(y1 - y2)
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}
func minimumDistance(word string) int {
n := len(word)
dp := make([][]int, n)
for i := range dp {
dp[i] = make([]int, 26)
for j := range dp[i] {
dp[i][j] = 1 << 30
}
}
for j := 0; j < 26; j++ {
dp[0][j] = 0
}
for i := 1; i < n; i++ {
cur := int(word[i] - 'A')
prev := int(word[i-1] - 'A')
d := getDistance(prev, cur)
for j := 0; j < 26; j++ {
dp[i][j] = min(dp[i][j], dp[i-1][j]+d)
if prev == j {
for k := 0; k < 26; k++ {
d0 := getDistance(k, cur)
dp[i][j] = min(dp[i][j], dp[i-1][k]+d0)
}
}
}
}
ans := 1 << 30
for j := 0; j < 26; j++ {
ans = min(ans, dp[n-1][j])
}
return ans
}
###C
int 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);
}
int minimumDistance(char* word) {
int n = strlen(word);
int** dp = (int**)malloc(n * sizeof(int*));
for (int i = 0; i < n; i++) {
dp[i] = (int*)malloc(26 * sizeof(int));
for (int j = 0; j < 26; j++) {
dp[i][j] = INT_MAX / 2;
}
}
for (int j = 0; j < 26; j++) {
dp[0][j] = 0;
}
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] = fmin(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] = fmin(dp[i][j], dp[i - 1][k] + d0);
}
}
}
}
int ans = INT_MAX / 2;
for (int j = 0; j < 26; j++) {
if (ans > dp[n - 1][j]) {
ans = dp[n - 1][j];
}
}
for (int i = 0; i < n; i++) {
free(dp[i]);
}
free(dp);
return ans;
}
###JavaScript
var minimumDistance = function(word) {
const n = word.length;
const getDistance = (p, q) => {
const x1 = Math.floor(p / 6), y1 = p % 6;
const x2 = Math.floor(q / 6), y2 = q % 6;
return Math.abs(x1 - x2) + Math.abs(y1 - y2);
};
const dp = new Array(n);
for (let i = 0; i < n; i++) {
dp[i] = new Array(26).fill(Math.floor(Number.MAX_SAFE_INTEGER / 2));
}
for (let j = 0; j < 26; j++) {
dp[0][j] = 0;
}
for (let i = 1; i < n; i++) {
const cur = word.charCodeAt(i) - 65;
const prev = word.charCodeAt(i - 1) - 65;
const d = getDistance(prev, cur);
for (let j = 0; j < 26; j++) {
dp[i][j] = Math.min(dp[i][j], dp[i - 1][j] + d);
if (prev === j) {
for (let k = 0; k < 26; k++) {
const d0 = getDistance(k, cur);
dp[i][j] = Math.min(dp[i][j], dp[i - 1][k] + d0);
}
}
}
}
let ans = Math.floor(Number.MAX_SAFE_INTEGER / 2);
for (let j = 0; j < 26; j++) {
ans = Math.min(ans, dp[n - 1][j]);
}
return ans;
};
###TypeScript
function minimumDistance(word: string): number {
const n = word.length;
const getDistance = (p: number, q: number): number => {
const x1 = Math.floor(p / 6), y1 = p % 6;
const x2 = Math.floor(q / 6), y2 = q % 6;
return Math.abs(x1 - x2) + Math.abs(y1 - y2);
};
const dp: number[][] = new Array(n);
for (let i = 0; i < n; i++) {
dp[i] = new Array(26).fill(Math.floor(Number.MAX_SAFE_INTEGER / 2));
}
for (let j = 0; j < 26; j++) {
dp[0][j] = 0;
}
for (let i = 1; i < n; i++) {
const cur = word.charCodeAt(i) - 65;
const prev = word.charCodeAt(i - 1) - 65;
const d = getDistance(prev, cur);
for (let j = 0; j < 26; j++) {
dp[i][j] = Math.min(dp[i][j], dp[i - 1][j] + d);
if (prev === j) {
for (let k = 0; k < 26; k++) {
const d0 = getDistance(k, cur);
dp[i][j] = Math.min(dp[i][j], dp[i - 1][k] + d0);
}
}
}
}
let ans = Math.floor(Number.MAX_SAFE_INTEGER / 2);
for (let j = 0; j < 26; j++) {
ans = Math.min(ans, dp[n - 1][j]);
}
return ans;
}
###Rust
impl Solution {
fn get_distance(p: i32, q: i32) -> i32 {
let x1 = p / 6;
let y1 = p % 6;
let x2 = q / 6;
let y2 = q % 6;
(x1 - x2).abs() + (y1 - y2).abs()
}
pub fn minimum_distance(word: String) -> i32 {
let n = word.len();
let word_bytes = word.as_bytes();
let mut dp = vec![vec![i32::MAX >> 1; 26]; n];
for j in 0..26 {
dp[0][j] = 0;
}
for i in 1..n {
let cur = (word_bytes[i] - b'A') as i32;
let prev = (word_bytes[i - 1] - b'A') as i32;
let d = Self::get_distance(prev, cur);
for j in 0..26 {
let j_i32 = j as i32;
dp[i][j] = dp[i][j].min(dp[i - 1][j].saturating_add(d));
if prev == j_i32 {
for k in 0..26 {
let d0 = Self::get_distance(k as i32, cur);
dp[i][j] = dp[i][j].min(dp[i - 1][k].saturating_add(d0));
}
}
}
}
let mut ans = i32::MAX >> 1;
for j in 0..26 {
ans = ans.min(dp[n - 1][j]);
}
ans
}
}
复杂度分析
-
时间复杂度：$O(|\Sigma|N)$。
-
空间复杂度：$O(|\Sigma|N)$。
登录
