Question

The following function accepts 2 strings, the 2nd (not 1st) possibly containing * s (asterisks). An * is a replacement for a string (empty, 1 char or more), it can appear appear (only in s2) once, twice, more or not at all, it cannot be adjacent to another * (ab**c), no need to check that.

public static boolean samePattern(String s1, String s2)

It returns true if strings are of the same pattern. It must be recursive, not use any loops, static or global variables. Also it s prohibited to use the method equals in the String class. Can use local variables and method overloading. Can use only these methods: charAt(i), substring(i), substring(i, j), length().

实例:

1: TheExamIsEasy; 2: "The*xamIs*y" ---> true
1: TheExamIsEasy; 2: "Th*mIsEasy*" ---> true
1: TheExamIsEasy; 2: "*" ---> true
1: TheExamIsEasy; 2: "TheExamIsEasy" ---> true
1: TheExamIsEasy; 2: "The*IsHard" ---> FALSE

我在很多小时的时间里一直在处理这个问题! 在 Java,我需要找到解决办法。

Answer 1

看见might,请。

www.un.org/Depts/DGACM/index_french.htm

但是,你有两个问题。

Answer 2

下面是你在 Java问题的复健、无 lo的解决办法:

static boolean samePattern(String s1, String s2) {
    return
        s2.isEmpty() ?
            s1.isEmpty()
            :
        s2.charAt(0) ==  *  ?
            samePattern(s1, s2.substring(1))
            || (!s1.isEmpty() && samePattern(s1.substring(1), s2))
            :
        !s1.isEmpty() && s2.charAt(0) == s1.charAt(0) ?
            samePattern(s1.substring(1), s2.substring(1))
            :
        false;
}
public static void main(String[] args) {
    String[] patterns = {
        "The*xamIs*y",    // true
        "Th*mIsEasy*",    // true
        "*",              // true
        "TheExamIsEasy",  // true
        "The*IsHard",     // false
    };
    for (String pattern : patterns) {
        System.out.println(samePattern("TheExamIsEasy", pattern));
    }
}

The algorithm

基本上,这里的重新定义是:

If s2 is empty, then it s samePattern if s1 is also empty
Otherwise s2 is not empty
- If it starts with *, then it s samePattern if
  - It s samePattern with the * removed
  - Or it s samePattern with a character removed from s1 (if there s one)
- Otherwise it starts with a regular character
  - If it matches the first character s1, then check if it s samePattern for the rest of s1, s2
  - Otherwise it s not samePattern, so it s false

Simplified version

此处为上述算法的简化版本:

static boolean samePatternSimplified(String s1, String s2) {
    if (s2.length() == 0) {
        return s1.length() == 0;
    } else if (s2.charAt(0) ==  * ) {
        return samePatternSimplified(s1, s2.substring(1))
           || (s1.length() != 0 && samePatternSimplified(s1.substring(1), s2));
    } else if (s1.length() != 0 && s2.charAt(0) == s1.charAt(0)) {
        return samePatternSimplified(s1.substring(1), s2.substring(1));
    } else {
        return false;
    }
}

API links

String.isEmpty()
- Returns true if, and only if, length() is 0.
JLS 15.25 Conditional Operator ?:
- This is the ?: operator used in the original solution
Java Language Guide/The for-each loop
- This is the for (String pattern : patterns) construct above

The algorithm

Simplified version

API links

友情链接