检查一个字符串是否为另一个字符串的子串。

Question

检查一个字符串是否为另一个字符串的子串。

6

我看到一篇关于检查一个字符串是否是另一个字符串的子串的好文章。

这个练习的内容如下：

编写一个程序，从命令行接收 2 个字符串参数。程序必须验证第二个字符串是否为第一个字符串的子串（不能使用substr、substring或任何其他标准函数，包括正则表达式库）。

第二个子字符串中的每个星号（*）表示它可以与第一个字符串的零个或多个字符匹配。

考虑以下示例：输入字符串1：abcd 输入字符串2：a*c 程序应该评估字符串2是字符串1的子串。

此外，如果星号（*）前面有反斜杠（\），则可以将其视为普通字符。在所有情况下，反斜杠（\）都被视为常规字符，除了在星号（*）之前。

我写了一个简单的应用程序，首先检查第二个字符串的长度是否不超过第一个字符串（但是当测试 ("ab", "a*b") 时会出现问题，这是正确的测试，但方法失败了）：

public static boolean checkCharactersCount(String firstString, String secondString) {
    return (firstString.length() > 0 && secondString.length() > 0) &&
            (firstString.length() > secondString.length());

...接下来验证的是一个子字符串：

public static boolean checkSubstring(String firstString, String secondString) {
    int correctCharCounter = 0;
    int lastCorrectCharAtIndex = -1;

    for (int i = 0; i < secondString.length(); i++) {
        for (int j = 0; j < firstString.length(); j++) {
            if (j > lastCorrectCharAtIndex) {

                if ((secondString.charAt(i) == firstString.charAt(j)) || secondString.charAt(i) == '*') {
                    correctCharCounter++;
                    lastCorrectCharAtIndex = j;
                }

                if (correctCharCounter >= secondString.length())
                    return true;
            }
        }
    }

    return false;
}

但是有两个问题：

我的代码不支持字符连续性（例如测试：checkSubstring("abacd", "bcd")返回true，但是这是错误的！- 应该返回false）
如何验证特殊符号"\*"？测试样例（checkSubstring("abc", "\b")

您对解决方案有什么想法？ :)

- ACz

1

旁注：转义规则有些奇怪，不允许指定一个反斜杠后跟一个通配符。 - Henry

@Henry 是的，写起来有点难；P 我们需要使用双反斜杠（"\")，这样才能将第二个反斜杠定义为真正的反斜杠或其他符号；P - ACz

1

\\*的意思是反斜杠（第一个）后面跟着一个字面上的星号。 - Henry

你不需要在第一个循环变量i的每次迭代中重置correctCharCounter吗？ - Yamuk

2

请注意，您的长度检查将排除“ab”和“a * b”，尽管它应该有效，因为星号可以代表零个字符。 - Max Vollmer

显示剩余3条评论

4个回答

1

我会分几个阶段来完成这个任务。

我们把潜在的子字符串称为p，包含子字符串s的字符串称为我们要测试的字符串。

把“包含”部分拆分成一系列问题，“p是否从s的第N个位置开始匹配？”；显然，你需要从第一个位置开始遍历s，以查看p是否与s的任何位置匹配。

在匹配过程中，我们有可能遇到一个“*”；在这种情况下，我们想知道“*”后面的p部分是否是匹配s中与p的前半部分相对应的部分的子字符串。这表明需要一个递归程序，以匹配要匹配的部分和字符串，并返回true/false。当你遇到一个“*”时，形成两个新字符串并调用自己。

如果你遇到一个\，那么你只需要继续使用下一个字符进行常规匹配，而不是进行递归调用。考虑到这一点，我认为最容易的方法是从原始的p中构建pPrime，这样当遇到反斜杠时，你可以删除它们，类似于从通配符匹配中删除星号。

我实际上还没有写过任何代码，因为你只是问了我的方法。

- arcy

很好的解决方案！没有反斜杠的临时字符串听起来不错；）我很好奇你将如何在代码中解决它。 - ACz

1

我觉得这是一个很好的挑战。这个练习真正迫使我们在语言和算法的非常低的层面上思考。没有lambda、没有stream、没有regex、没有find、没有substring，什么都没有。只有旧的CharAt、一些for循环等等。本质上，我制作了一个查找方法，该方法查找要查找的字符串的第一个字符，然后进行另一个查找，从那一点开始考虑您的规则。如果失败，它会回到找到的第一个索引，加1，直到字符串的末尾为止，执行多少次迭代。如果没有找到匹配项，则应返回false。如果只找到一个，则足以将其视为子字符串。最重要的边角情况在计算开始时考虑，以便如果检测到假定为某个确定的东西，它就不会继续进行。因此，'*'单独表示任何字符匹配，我们可以用\来转义它。我试图包括大多数边角情况，这确实是一个挑战。我不完全确定我的代码是否涵盖了您的所有情况，但它应该涵盖相当多的情况。我真的想帮助您，所以这是我的方法，这是我的代码：

package com.jesperancinha.string;

public class StringExercise {

    private static final char ASTERISK = '*';
    private static final char BACKSLASH = '\\';

    public boolean checkIsSubString(String mainString, String checkString) {
        int nextIndex = getNextIndex(0, checkString.charAt(0), mainString);
        if (nextIndex == -1) {
            return false;
        }
        boolean result = checkFromIndex(nextIndex, mainString, checkString);
        while (nextIndex < mainString.length() - 1 && nextIndex > -1) {
            if (!result) {
                nextIndex = getNextIndex(nextIndex + 1, checkString.charAt(0), mainString);
                if (nextIndex > -1) {
                    result = checkFromIndex(nextIndex, mainString, checkString);
                }
            } else {
                return result;
            }
        }
        return result;
    }

    private int getNextIndex(int start, char charAt, String mainString) {
        if (charAt == ASTERISK || charAt == BACKSLASH) {
            return start;
        }
        for (int i = start; i < mainString.length(); i++) {
            if (mainString.charAt(i) == charAt) {
                return i;
            }
        }
        return -1;
    }

    private boolean checkFromIndex(int nextIndex, String mainString, String checkString) {
        for (int i = 0, j = 0; i < checkString.length(); i++, j++) {
            if (i < (checkString.length() - 2) && checkString.charAt(i) == BACKSLASH
                    && checkString.charAt(i + 1) == ASTERISK) {
                i++;
                if (mainString.charAt(j + nextIndex) == BACKSLASH) {
                    j++;
                }
                if (checkString.charAt(i) != mainString.charAt(j + nextIndex)) {
                    return false;
                }
            }
            if (i > 0 && checkString.charAt(i - 1) != BACKSLASH
                    && checkString.charAt(i) == ASTERISK) {
                if (i < checkString.length() - 1 && (j + nextIndex) < (mainString.length() - 1)
                        && checkString.charAt(i + 1) !=
                        mainString.charAt(j + nextIndex + 1)) {
                    i--;
                } else {
                    if (j + nextIndex == mainString.length() - 1
                            && checkString.charAt(checkString.length() - 1) != ASTERISK
                            && checkString.charAt(checkString.length() - 2) != BACKSLASH) {
                        return false;
                    }
                }
            } else {
                if ((j + nextIndex) < (mainString.length() - 2) &&
                        mainString.charAt(j + nextIndex)
                                != checkString.charAt(i)) {
                    return false;
                }
            }
        }
        return true;
    }

}

我已经编写了一组单元测试，但如果我在这里放置整个类，它会太长，而我想要展示的只是我在单元测试中实现的测试用例。以下是我为此案例编写的单元测试的精简版本：

package com.jesperancinha.string;

import static org.assertj.core.api.Assertions.assertThat;

import org.junit.jupiter.api.Test;

class StringExerciseMegaTest {

    @Test
    void checkIsSubString() {
        StringExercise stringExercise = new StringExercise();
        boolean test = stringExercise.checkIsSubString("abcd", "a*c");
        assertThat(test).isTrue();
        test = stringExercise.checkIsSubString("abcd", "a\\*c");
        assertThat(test).isFalse();
        test = stringExercise.checkIsSubString("a*c", "a\\*c");
        assertThat(test).isTrue();
        test = stringExercise.checkIsSubString("aasdsadasa*c", "a\\*c");
        assertThat(test).isTrue();
        test = stringExercise.checkIsSubString("aasdsadasa*csdfdsfdsfdsf", "a\\*c");
        assertThat(test).isTrue();
        test = stringExercise.checkIsSubString("aasdsadasa**csdfdsfdsfdsf", "a\\*c");
        assertThat(test).isFalse();
        test = stringExercise.checkIsSubString("aasdsadasa**csdfdsfdsfdsf", "a*c");
        assertThat(test).isTrue();
        test = stringExercise.checkIsSubString("aasdsadasa*csdfdsfdsfdsf", "a*c");
        assertThat(test).isTrue();
        test = stringExercise.checkIsSubString("aasdweriouiauoisdf9977675tyhfgh", "a*c");
        assertThat(test).isFalse();
        test = stringExercise.checkIsSubString("aasdweriouiauoisdf9977675tyhfgh", "dwer");
        assertThat(test).isTrue();
        test = stringExercise.checkIsSubString("aasdweriouiauoisdf9977675tyhfgh", "75tyhfgh");
        assertThat(test).isTrue();
        test = stringExercise.checkIsSubString("aasdweriou\\iauoisdf9977675tyhfgh", "riou\\iauois");
        assertThat(test).isTrue();
        test = stringExercise.checkIsSubString("aasdweriou\\*iauoisdf9977675tyhfgh", "riou\\\\*iauois");
        assertThat(test).isTrue();
        test = stringExercise.checkIsSubString("aasdweriou\\*iauoisdf9\\*977675tyhfgh", "\\\\*977675tyhfgh");
        assertThat(test).isTrue();
        test = stringExercise.checkIsSubString("aasdweriou\\*iauoisdf9\\*977675tyhfgh", "\\*977675tyhfgh");
        assertThat(test).isTrue();
        test = stringExercise.checkIsSubString("\\*aasdweriou\\*iauoisdf9\\*977675tyhfgh", "\\*aasdwer");
        assertThat(test).isTrue();
        test = stringExercise.checkIsSubString("*aasdweriou\\*iauoisdf9\\*977675tyhfgh", "*aasdwer");
        assertThat(test).isTrue();
        test = stringExercise.checkIsSubString("abcd", "bc");
        assertThat(test).isTrue();
        test = stringExercise.checkIsSubString("abcd", "zbc");
        assertThat(test).isFalse();
        test = stringExercise.checkIsSubString("abcd", "*bc*");
        assertThat(test).isTrue();
        test = stringExercise.checkIsSubString("*bcd", "\\*bc*");
        assertThat(test).isTrue();
        test = stringExercise.checkIsSubString("abcd", "a*c");
        assertThat(test).isTrue();
        test = stringExercise.checkIsSubString("abcd", "az*bc");
        assertThat(test).isFalse();
    }
}

- Joao Esperancinha

1

太棒了！是个不错的挑战，需要检查很多情况，如空字符串、无符号、字符计数、特殊字符等等... 这个练习看起来很简单，但如果我们开始编码，就会发现有很多情况和 if 语句需要检查 ;D 给我一点时间来检查这段代码，它看起来非常复杂。 - ACz

1

@ACz，谢谢！很高兴能帮忙！ - Joao Esperancinha

0

我的解决方案看起来像这样，我对每个部分都进行了注释，希望你能理解。

public static void main(String [] args) throws Exception {
        System.err.println(contains("bruderMusssLos".toCharArray(),"Mu*L*".toCharArray()));
}

public static boolean contains(char [] a, char [] b) {

    int counterB = 0; // correct characters
    char lastChar = '-'; //last Character encountered in B

    for(int i = 0; i < a.length; i++) {

        //if last character * it can be 0 to infinite characters
        if(lastChar == '*') {

            //if next characters in a is next in b reset last char
            // this will be true as long the next a is not the next b
            if(a[i] == b[counterB]) {
                lastChar = b[counterB];
                counterB++;

            }else {
                counterB++;
            }

        }else {

            //if next char is * and lastchar is not \ count infinite to next hit
            //otherwise * is normal character
            if(b[counterB] == '*' && lastChar != '\\') {
                lastChar = '*';
                counterB++;
            }else {
                //if next a is next b count
                if(a[i] == b[counterB]) {
                    lastChar = b[counterB];
                    counterB++;
                }else {
                    //otherwise set counter to 0
                    counterB = 0;
                }                   
            }

        }

        //if counterB == length a contains b
        if(counterB == b.length)
            return true;

    }


    return false;
}

目前的测试返回为true，例如:)

- user8439161

1

好的，我意识到它对于 * = 0 的字符无法工作，我的错。因此需要进行额外的检查，但除此之外，这对于所有 * > 0 的字符和数组长度大于0的情况都有效。 - user8439161

让我检查一下，我会带回答案的。 - ACz

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Abhishek Oza · Accepted Answer

尝试这个：（添加注释以进行解释）

// only for non empty Strings
public boolean isSubString(String string1,String string2)
{
    // step 1: split by *, but not by \*
    List<String>list1 = new ArrayList<String>();
    char[]cs = string2.toCharArray();
    int lastIndex = 0 ;
    char lastChar = 0 ;
    int i = 0 ;
    for(; i < cs.length ; ++i)
    {
        if(cs[i]=='*' && lastChar!='\\')
        {
            list1.add(new String(cs,lastIndex,i-lastIndex).replace("\\*", "*"));
            //earlier buggy line:
            //list1.add(new String(cs,lastIndex,i-lastIndex));
            lastIndex = i + 1 ;
        }
        lastChar = cs[i];
    }
    if(lastIndex < i )
    {
        list1.add(new String(cs,lastIndex,i-lastIndex).replace("\\*", "*"));
    }
    // step 2: check indices of each string in the list
    // Note: all indices should be in proper order.
    lastIndex = 0;
    for(String str : list1)
    {
        int newIndex = string1.indexOf(str,lastIndex);
        if(newIndex < 0)
        {
            return false;
        }
        lastIndex = newIndex+str.length();
    }
    return true;
}

如果您不允许使用 String.indexOf()，那么请编写一个函数 public int indexOf(String string1,String string2, int index2) 来替换此语句。

int newIndex = string1.indexOf(str,lastInxdex);

使用这个语句：

int newIndex = indexOf(string1, str,lastInxdex);

附录A：我测试过的代码：

package jdk.conf;

import java.util.ArrayList;
import java.util.List;

public class Test01 {
    public static void main(String[] args)
    {
        Test01 test01 = new Test01();
        System.out.println(test01.isSubString("abcd", "a*c"));
        System.out.println(test01.isSubString("abcd", "bcd"));
        System.out.println(test01.isSubString("abcd", "*b"));
        System.out.println(test01.isSubString("abcd", "ac"));
        System.out.println(test01.isSubString("abcd", "bd"));
        System.out.println(test01.isSubString("abcd", "b*d"));
        System.out.println(test01.isSubString("abcd", "b\\*d"));
        System.out.println(test01.isSubString("abcd", "\\*d"));
        System.out.println(test01.isSubString("abcd", "b\\*"));

        System.out.println(test01.isSubString("a*cd", "\\*b"));
        System.out.println(test01.isSubString("", "b\\*"));
        System.out.println(test01.isSubString("abcd", ""));

        System.out.println(test01.isSubString("a*bd", "\\*b"));
    }
    // only for non empty Strings
    public boolean isSubString(String string1,String string2)
    {
        // step 1: split by *, but not by \*
        List<String>list1 = new ArrayList<String>();
        char[]cs = string2.toCharArray();
        int lastIndex = 0 ;
        char lastChar = 0 ;
        int i = 0 ;
        for(; i < cs.length ; ++i)
        {
            if(cs[i]=='*' && lastChar!='\\')
            {
                list1.add(new String(cs,lastIndex,i-lastIndex).replace("\\*", "*"));
                lastIndex = i + 1 ;
            }
            lastChar = cs[i];
        }
        if(lastIndex < i )
        {
            list1.add(new String(cs,lastIndex,i-lastIndex).replace("\\*", "*"));
        }
        // step 2: check indices of each string in the list
        // Note: all indices should be in proper order.
        lastIndex = 0;
        for(String str : list1)
        {
            int newIndex = string1.indexOf(str,lastIndex);
            if(newIndex < 0)
            {
                return false;
            }
            lastIndex = newIndex+str.length();
        }
        return true;
    }
}

输出：

true
true
true
false
false
true
false
false
false
false
false
true
true