所以我整天都在尝试解决这个任务,就是无法完成。
以下函数接受 2 个字符串,第二个(不是第一个)可能包含*
's(星号)。
an*
是字符串的替换(空,1 个字符或更多),它可以出现(仅在 s2 中)一次、两次、更多或根本不出现,它不能与另一个相邻*
(ab**c
),无需检查。
public static boolean samePattern(String s1, String s2)
如果字符串具有相同的模式,则返回 true。
它必须是递归的,不能使用任何循环、静态和全局变量。可以使用局部变量和方法重载。
只能使用以下方法:charAt(i)
, substring(i)
, substring(i, j)
, length()
.
例子:
1 TheExamIsEasy
:;2: The*xamIs*y
→ 真
1: TheExamIsEasy
; 2: Th*mIsEasy*
→ 真
1: TheExamIsEasy
; 2: *
→ 真
1: TheExamIsEasy
; 2: TheExamIsEasy
→ 真
1: TheExamIsEasy
; 2:The*IsHard
→假
我尝试使用逐个比较字符,charAt
直到遇到星号,然后通过比较连续字符 ( i+1
) 与s1
at 位置的字符来检查星号是否为空i
,如果为真 - 继续递归i+1
作为s2
&的计数器i
作为计数器s1
;
如果为假 - 继续递归i+1
作为两者的计数器。
继续此操作,直到找到另一个星号或字符串结尾。
我不知道,我的大脑失去了对事物的追踪,无法集中注意力,任何指针/提示?我在正确的方向吗?
此外,据说要使用回溯技术来解决这个问题。
到目前为止我的代码(即使在理论上也不能完成这项工作):
public static boolean samePattern(String s1, String s2) {
if (s1.equals(s2) || s2 == "*") {
return true;
}
return samePattern(s1, s2, 1);
}
public static boolean samePattern(String s1, String s2, int i)
{
if (s1.equals(s2))
return true;
if (i == s2.length() - 1) // No *'s found -- not same pattern.
return false;
if (s1.substring(0, i).equals(s2.substring(0, i)))
samePattern(s1, s2, i+1);
else if (s2.charAt(i-1) == '*')
samePattern(s1.substring(0, i-1), s2.substring(0, i), 1); // new smaller strings.
else
samePattern(s1.substring(1), s2, i);
}