确定字符移动数以得到单词
提问于 2014-09-18 22:27:29
假设你得到了一个词
向日葵
您只能对它执行一种操作类型，选择一个字符并将其移动到前面。因此，例如，如果你选择'f'，这个词将是"fsunlower“。
您可以进行一系列这样的操作。
- fsunlower (把f移到前面)
- wfsunloer (向前移动)
- fwsunloer (再次将f移到前面)
问题是，给定派生词和原始单词，得到所需的最小操作数。因此，如果输入字符串为"fwsunloer"，“向日葵”，则输出为3。
回答 1
Stack Overflow用户
发布于 2014-09-18 22:41:27
这个问题等价于:给定字符串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包含相同字符集的假设。否则，您需要在使用该函数之前检查它。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/25927648
复制相关文章
点击加载更多
腾讯云开发者
