构建字符串算法

Question

我正在努力解决和理解构建字符串问题，

这段代码通过了6个测试用例，然后失败了，我得到了一个失败的测试用例，但我不明白为什么它失败了，有人能解释为什么吗？

测试用例

Input
a = 7890 
b = 7891
s = acbcrsjcrscrsjcrcbcrsjcrscrsjccbcrsjcrscrsjcrcbcrsjrscrsjcrcbcrsjcrscrsjccbcrsjcrscrsjcrcbcsbcbcrsjh

预期：126246

实际上：126247

static int buildString(int a, int b, String s) {
int result = 0;
String initial = "";
while (!s.equals("")) {
final String substring = s.substring(0, 1);
if (!initial.contains(substring)) {
initial += substring;
result += a;
s = s.substring(1);
} else {
String last = "";
for (int i = 1; i <= s.length(); i++) {
final String substring1 = s.substring(0, i);
if (initial.contains(substring1)) {
last = substring1;
} else {
break;
}
}
if (last.equals(substring) || b > (last.length() * a)) {
initial += substring;
result += a;
s = s.substring(1);
} else {
initial += last;
result += b;
s = s.substring(last.length());
}
}
}
return result;
}

Answer 1

由于您使用的是贪婪算法，该算法尽可能附加最长的子字符串(操作b(，如果操作b不可能，则在末尾添加一个字符(操作a(，步骤如下。

aacbcrsjcrs[/tr>acbcrsjcrscrsjcrcbcrsjcrsjccbcrsjccrcrcrscjccrcrcbcrsj>

步骤		操作	结果
1	a
2	a	ac
3	a	acb
4	a	acbc
5	a	acbcr
6	a	acbcrs
7	a	acbcrsj
8	b
9	b	acbcrsjcrscrsjcr
10	b	acbcrsjcrscrsjcrcbcrsjcrssjc
11	b
12	b	acbcrsjcrscrsjcrcbcrsjccbcrsjccrcrcrcrcsjrscrsjccrcbcrcrsjcrscrsjscrcrcrccc
13	a	acbcrsjcrscrsjcrcbcrsjcrsscccrsjccrcrcrcrccrsjrscrsjccrcbcrcrsjcrssccrssccrccrsjcrccrcrcbcs
14	b	acbcrsjcrscrsjcrcbcrsjcrsscccrsjccrcrcrcrccrsjcrsscrsjcrcrcbcsbc
15	b	acbcrsjcrscrsjcrcbcrsjcrsjccbcrsjccrcrcrcrscrsjrscrsjccrcbcrrsjcrsscccrsjcrsjccrcrcbcrsjcrcrcrcbcbcrsj
16	a	acbcrsjcrscrsjcrcbcrsjcrsscrsjccrcrcrcrscrsjrscrsjccrcbcrrsjcrssccrcrcrcrcscrsjcrssrcrcrccrscrcrcrcrc

这里有一个简单的Java迭代解决方案。

---

代码

BuildString.java

public class BuildString {
/**
* Build a string.
*
* @param s the string to build,
* @param a point to append a char,
* @param b point to append a substring of existing part, b >= a,
* @return total point used,
*/
public static int build(String s, int a, int b) {
return build(s, a, b, new StringBuilder());
}
/**
* Build step by step, via iteration.
*
* @param s
* @param a
* @param b
* @param sb the built part,
* @return
*/
private static int build(String s, int a, int b, StringBuilder sb) {
int point = 0;
while (sb.length() < s.length()) {
String subStr = findMaxSubStr(sb, s);
if (subStr != null) {
sb.append(subStr);
point += b;
} else {
sb.append(s.charAt(sb.length()));
point += a;
}
}
return point;
}
/**
* Find next max substring with length >= 2.
*
* @param sb the existing part,
* @param s  the original string.
* @return next max substring with length >= 2, or null if not exists,
*/
private static String findMaxSubStr(StringBuilder sb, String s) {
// TODO ... improve with cache ?
int sLen = s.length();
int sbLen = sb.length();
for (int i = sLen - sbLen; i > 1; i--) {
String target = s.substring(sbLen, sbLen + i);
if (sb.indexOf(target) >= 0) return target; // found,
}
return null; // not found,
}
}

BuildStringTest.java
(测试用例-通过TestNG(

import org.testng.Assert;
import org.testng.annotations.Test;
import static org.testng.Assert.*;
public class BuildStringTest {
@Test
public void testBuild() {
testOnce("aabaacaba", 4, 5, 26);
testOnce("bacbacacb", 8, 9, 42);
}
@Test
public void testCorner() {
testOnce("", 4, 5, 0); // empty string,
testOnce("a", 4, 5, 4); // single char,
}
private void testOnce(String s, int a, int b, int expectedPoint) {
int point = BuildString.build(s, a, b);
System.out.printf("s = '%s', a = %d, b = %d, expected point: %d,t actual point: %dn", s, a, b, expectedPoint, point);
Assert.assertEquals(point, expectedPoint);
}
}

---

复杂性

• 时间：O(n^2)
• 空间：O(n)

---

TODO

• 我想可以使用某种缓存来加快搜索下一个最大子串的速度，以提高时间复杂性