确定字符移动数以得到单词

Question

假设你得到了一个词

向日葵

您只能对它执行一种操作类型，选择一个字符并将其移动到前面。因此，例如，如果你选择'f'，这个词将是"fsunlower“。

您可以进行一系列这样的操作。

1. fsunlower (把f移到前面)
2. wfsunloer (向前移动)
3. fwsunloer (再次将f移到前面)

问题是，给定派生词和原始单词，得到所需的最小操作数。因此，如果输入字符串为"fwsunloer"，“向日葵”，则输出为3。

Answer 1

这个问题等价于:给定字符串A和B，找到字符串A的最长后缀，即字符串B的sub-sequence。因为，如果我们知道哪些n个字符需要移动，我们只需要n步。因此，我们需要找到的是不需要移动的最大字符数，这相当于A中最长的后缀。

因此，对于给定的示例，最长的后缀是sunlor。

Java代码：

public static void main(String[] args) {
    System.out.println(minOp("ewfsunlor", "sunflower"));
}

public static int minOp(String A, String B) {
    int n = A.length() - 1;//Start from the end of String A;
    int pos = B.length();
    int result = 0;
    while (n >= 0) {
        int nxt = -1;
        for (int i = pos - 1; i >= 0; i--) {
            if (B.charAt(i) == A.charAt(n)) {
                nxt = i;
                break;
            }
        }
        if (nxt == -1) {
            break;
        }
        result++;
        pos = nxt;
        n--;
    }
    return B.length() - result;
}

结果：

3

具有n的时间复杂度O(n)是字符串A的长度。

注意事项：该算法基于A和B包含相同字符集的假设。否则，您需要在使用该函数之前检查它。