在String1中匹配String2的字符出现和模式。

Question

在String1中匹配String2的字符出现和模式。

8

我在暑期实习的电话面试中被问到这个问题，并尝试用Java提出了一个n*m复杂度的解决方案（虽然不太准确）。我的函数接受两个字符串，假设是“common”和“cmn”。如果“common”中的‘c’、‘m’、‘n’按照相同顺序出现，则应该返回True。但是如果参数是“common”和“omn”，则应该返回False，因为即使它们按照相同顺序出现，但是‘m’也出现在‘o’之后（这违反了模式匹配条件）。我已经使用HashMaps和Ascii数组进行了工作，但是还没有得到令人信服的解决方案！从我到目前为止所读的内容来看，这是否与Boyer-Moore或Levenshtein距离算法有关？希望在stackoverflow上得到解脱！：）编辑：一些答案谈论缩短单词长度或创建哈希集。但根据我的理解，这道题不能用哈希集完成，因为第一个字符串中每个字符的出现/重复都有其自身的意义。通过的条件包括“con”、“cmn”、“cm”、“cn”、“mn”、“on”、“co”。否定的条件可能看起来不同，例如“com”、“omn”、“mon”、“om”。这些都是错误的/失败的，因为“o”既出现在“m”之前又出现在“m”之后。另一个例子是“google”和“ole”会通过，但“google”和“gol”会失败，因为“o”也出现在“g”之前！

- MadTest

2

如果我理解正确，como会匹配，但cmo不会，您能解释一下匹配的规则是什么吗？ - RonK

6

“...但是在'o'后面也出现了'm'（这违反了模式匹配条件）…”-这是什么意思？在您的模式“omn”中，“m”也出现在“o”之后。为什么它会“未能满足匹配条件”？您需要提供更精确的匹配条件描述。您目前的描述似乎没有太多意义。这句话的意思是，在给定的模式 omn 中，如果字符串中出现了字母 m 排在字母 o 后面，那么这个字符串就不符合该模式的匹配条件。需要提供一个更准确的匹配条件描述，以便理解这个模式。 - AnT stands with Russia

这些问题后来在我的脑海中浮现，但在面试紧张和匆忙完成的情况下，我无法提出 :( @AndreyT- 无论如何，我的理解是- 如果要比较的字符串是“omn”，那么'o,m,n'以相同的顺序出现，但如果您的算法检查'o'是否在'm'之前出现，则'o'也会在'm'之后出现，这可能是它们出现顺序的失败条件。我希望我让它更清楚了？ - MadTest

1

@MadTest 这是谷歌面试题吗？ - SuperMan

只是确认一下，'mo'会返回False吗？ - NirmalGeo

如果“第二个”字符串包含重复字符呢？说实话，我怀疑面试官本意是要求你编写一个简单的最长公共子串算法，但他/她可能在解释所需内容方面出了问题，或者你误解了。 - j_random_hacker

8个回答

2

一个很好的问题，经过几个小时的研究，我想我已经找到了解决方案。首先让我试着用不同的方法来解释这个问题。 需求： 我们考虑相同的例子“common”（主字符串）和“cmn”（子字符串）。首先，我们需要明确的是任何字符都可以在主字符串和子字符串中重复，并且由于我们关注的是模式，因此字符的索引起着重要的作用。所以我们需要知道：

字符的索引（最小和最大）

让我们把这个放在一边，然后继续检查模式。对于单词common，我们需要找出特定模式cmn是否存在。与common可能的不同模式为：- （优先级应用）

c -> o
c -> m
c -> n
o -> m
o -> o
o -> n
m -> m
m -> o
m -> n
o -> n

任何时候都必须满足这种优先级和比较。由于优先级起着巨大的作用，我们需要拥有每个唯一字符的索引，而不是存储不同的模式。 解决方案： 解决方案的第一部分是创建一个哈希表，具有以下标准：

将主字符串的每个字符作为键创建哈希表
哈希表中唯一键的每个条目将存储两个索引，即lowerIndex和higherIndex
循环遍历主字符串，并为每个新字符更新哈希表中的lowerIndex的新条目，该条目包含主字符串中当前字符的索引。
如果发生碰撞，请使用higherIndex条目更新当前索引，直到字符串的结尾

模式匹配的第二个和主要部分：

Set Flag as False
Loop through the subString and for every character as the key, retreive the details from the Hash.
Do the same for the very next character.

Just before loop increment, verify two conditions

If highestIndex(current character) > highestIndex(next character) Then
   Pattern Fails, Flag <- False, Terminate Loop
   // This condition is applicable for almost all the cases for pattern matching

Else If lowestIndex(current character) > lowestIndex(next character) Then
   Pattern Fails, Flag <- False, Terminate Loop
   // This case is explicitly for cases in which patterns like 'mon' appear

Display the Flag

注意：由于我对Java不是很熟悉，所以没有提交代码。但是有人可以尝试实现我的想法。

- NirmalGeo

@Nirmal-感谢你的解决方案！我发现Hashtable唯一的问题是它们在创建时需要时间且不太可预测，虽然访问时间肯定是O(1)！这里我们将不得不创建两个Hashtable来存储最小和最大索引，或者遇到碰撞来更新它们 :) - MadTest

1

我自己用了一种低效的方法来解决这个问题，但它确实给出了准确的结果！如果有人能从中找出一种高效的代码/算法，我将不胜感激！

创建一个名为“Check”的函数，它接受两个字符串作为参数。检查字符串2的每个字符在字符串1中的出现顺序是否正确。

从字符串p中获取字符0，并遍历字符串s以找到其第一次出现的索引。
遍历填充好的ascii数组，查找任何值大于第一次出现的索引。
进一步遍历以找到最后一次出现并更新ascii数组
从字符串p中获取字符1，并遍历字符串s以找到它在字符串s中第一次出现的索引
遍历已填充好的ascii数组以查找任何值大于第一次出现的索引。如果找到返回False。
进一步遍历以找到最后一次出现并更新ascii数组

可以看出，这是一种暴力方法......我猜时间复杂度是O(N^3)

public class Interview
{
    public static void main(String[] args)
{
    if (check("google", "oge"))
        System.out.println("yes");
    else System.out.println("sorry!");
}

 public static boolean check (String s, String p) 
{   

     int[] asciiArr =  new int[256];    
     for(int pIndex=0; pIndex<p.length(); pIndex++) //Loop1 inside p
     {
        for(int sIndex=0; sIndex<s.length(); sIndex++) //Loop2 inside s
        {
            if(p.charAt(pIndex) == s.charAt(sIndex))    
            {
                asciiArr[s.charAt(sIndex)] = sIndex; //adding char from s to its Ascii value

                for(int ascIndex=0; ascIndex<256; )     //Loop 3 for Ascii Array
                {
                    if(asciiArr[ascIndex]>sIndex)           //condition to check repetition
                    return false;
                    else ascIndex++;
                }
            }
        }
     }
    return true;
}
}

- MadTest

如果复杂性不是问题，那么这就是一个直截了当的问题。 - NirmalGeo

我同意，但我发布这个问题是想知道是否有任何特定的算法或方法来解决这种类型的问题？ - MadTest

0

这不是可以在O(n log n)的时间复杂度内完成吗？

第一步，通过消除所有出现在右侧的字符来缩小字符串。严格来说，你只需要在检查的字符串中消除字符。

/** Reduces the maximal subsequence of characters in container that contains no
 * character from container that appears to the left of the same character in
 * container.  E.g. "common" -> "cmon", and "whirlygig" -> "whrlyig".
 */
static String reduceContainer(String container) {
  SparseVector charsToRight = new SparseVector();  // Like a Bitfield but sparse.
  StringBuilder reduced = new StringBuilder();
  for (int i = container.length(); --i >= 0;) {
    char ch = container.charAt(i);
    if (charsToRight.add(ch)) {
      reduced.append(ch);
    }
  }
  return reduced.reverse().toString();
}

第二步，检查包含关系。

static boolean containsInOrder(String container, String containee) {
  int containerIdx = 0, containeeIdx = 0;
  int containerLen = container.length(), containeeLen == containee.length();
  while (containerIdx < containerLen && containeeIdx < containeeLen) {
    // Could loop over codepoints instead of code-units, but you get the point...
    if (container.charAt(containerIdx) == containee.charAt(containeeIdx)) {
      ++containeeIdx;
    }
    ++containerIdx;
  }
  return containeeIdx == containeeLen;
}

回答你的第二个问题，Levenshtein距离不会对你有所帮助，因为它具有这样的属性：如果你交换参数，输出结果是相同的，但是你想要的算法却不是这样的。

- Mike Samuel

这个例子中会返回true，但实际上应该返回false——containsInOrder("common", "omn")=true。 - RonK

将编辑以展示如何添加一个 pass，该 pass 可以从容器中删除所有在字符串后面出现的字母。 - Mike Samuel

@Mike- 感谢您的回复，但我之前尝试过类似的逻辑，发现它失败了。假设字符串是“common”，“cmo”...根据您的逻辑，它会通过，因为“cmon”是缩减后的字符串。但它应该失败，因为在原始字符串中'o'也出现在'm'之前。 - MadTest

我理解的是必须跟踪和验证两个字符串中每个字符的索引。当以下条件满足时，它将通过测试：1. 第二个字符串中的每个字符以与原始字符串相同的方式出现！但是，当第一个字符串中有重复字符时，复杂度会增加。应该如何处理？ - MadTest

0

我用了另一种方法尝试了一下，现在分享我的解决方案。

public class PatternMatch {

public static boolean matchPattern(String str, String pat) {

    int slen = str.length();
    int plen = pat.length();
    int prevInd = -1, curInd;
    int count = 0;

    for (int i = 0; i < slen; i++) {

        curInd = pat.indexOf(str.charAt(i));


        if (curInd != -1) {

            if(prevInd == curInd)
                continue;
            else if(curInd == (prevInd+1))
                count++;
            else if(curInd == 0)
                count = 1;
            else count = 0;

            prevInd = curInd;
        }


        if(count == plen)
            return true;

    }

    return false;
}

public static void main(String[] args) {

    boolean r = matchPattern("common", "on");
    System.out.println(r);
}

}

- FourOfAKind

0

public class StringPattern {
    public static void main(String[] args) {
        String inputContainer = "common";
        String inputContainees[] = { "cmn", "omn" };
        for (String containee : inputContainees)
            System.out.println(inputContainer + " " + containee + " "
                    + containsCommonCharsInOrder(inputContainer, containee));

    }

    static boolean containsCommonCharsInOrder(String container, String containee) {
        Set<Character> containerSet = new LinkedHashSet<Character>() {
            // To rearrange the order
            @Override
            public boolean add(Character arg0) {
                if (this.contains(arg0))
                    this.remove(arg0);
                return super.add(arg0);
            }
        };
        addAllPrimitiveCharsToSet(containerSet, container.toCharArray());
        Set<Character> containeeSet = new LinkedHashSet<Character>();
        addAllPrimitiveCharsToSet(containeeSet, containee.toCharArray());

        // retains the common chars in order
        containerSet.retainAll(containeeSet);
        return containerSet.toString().equals(containeeSet.toString());

    }

    static void addAllPrimitiveCharsToSet(Set<Character> set, char[] arr) {
        for (char ch : arr)
            set.add(ch);
    }

}

输出：

common cmn true
common omn false

- Emil

谢谢回复，但它返回了“TRUE”对于“mon”，这实际上是一个错误的条件！ :( - MadTest

@MadTest：为什么它应该是假的？你能解释一下吗？ - Emil

0

我认为这是我曾经编写过的最糟糕的代码之一，或者是stackoverflow上最糟糕的代码示例之一...但是你知道吗...所有的条件都得到了满足！
没有算法能真正满足需求，所以我只使用了暴力方法...试试看...
而且我对空间和时间复杂度并不在意...我的目标首先是尝试解决它...也许以后再改进它！

public class SubString {

    public static void main(String[] args) {
        SubString ss = new SubString();
        String[] trueconditions = {"con", "cmn", "cm", "cn", "mn", "on", "co" };
        String[] falseconditions = {"com", "omn", "mon", "om"};

        System.out.println("True Conditions : ");
        for (String str : trueconditions) {
            System.out.println("SubString? : " + str + " : " + ss.test("common", str));
        }
        System.out.println("False Conditions : ");
        for (String str : falseconditions) {
            System.out.println("SubString? : " + str + " : " + ss.test("common", str));
        }
        System.out.println("SubString? : ole : " + ss.test("google", "ole"));
        System.out.println("SubString? : gol : " + ss.test("google", "gol"));
    }

    public boolean test(String original, String match) {
        char[] original_array = original.toCharArray();
        char[] match_array = match.toCharArray();

        int[] value = new int[match_array.length];
        int index = 0;
        for (int i = 0; i < match_array.length; i++) {
            for (int j = index; j < original_array.length; j++) {
                if (original_array[j] != original_array[j == 0 ? j : j-1] && contains(match.substring(0, i), original_array[j])) {

                    value[i] = 2;
                } else {
                    if (match_array[i] == original_array[j]) {
                        if (value[i] == 0) {
                            if (contains(original.substring(0, j == 0 ? j : j-1), match_array[i])) {
                                value[i] = 2;
                            } else {
                                value[i] = 1;
                            }
                        }
                        index = j + 1;
                    }
                }
            }
        }
        for (int b : value) {
            if (b != 1) {
                return false;
            }
        }
        return true;
    }

    public boolean contains(String subStr, char ch) {
        for (char c : subStr.toCharArray()) {
            if (ch == c) {
                return true;
            }
        }
        return false;
    }
}

-IvarD

- topgun_ivard

0

我认为这不是对你的计算机科学基础知识的测试，而更多地涉及到你在Java编程环境中实际操作的能力。

你可以将第二个参数构建成一个正则表达式，例如...

omn -> o.*m[^o]*n

...然后通过使用String.matches(...)或使用Pattern类来测试候选字符串。

通用形式下，RegExp的构造应该沿着以下方向进行。

exp -> in[0].* + 对于每个x：2 -> in.lenght { (in[x-1] + [^in[x-2]]* + in[x]) }

例如：

demmn -> d.*e[^d]*m[^e]*m[^m]*n

- Adrian Regan

你不能使用像你的正则表达式那样简单的方式来解决它，因为“mon”应该会失败（而派生的.*m.*o.*n.*不会）。但是可能可以通过更复杂的正则表达式来解决，其中你将.替换为“前面或后面的模式字符或不在模式中的任何字符”。所以类似于[^on]*m[^n]*o[^m]*n[^mo]*这样的东西（我不是一个正则表达式专家）。 - raymi

实际上，你是正确的，我会使用更好的RegExp更新答案。 - Adrian Regan

我认为你必须在NOT表达式（[^]）中包含每个未按正确顺序排列的字符（即不是NOT表达式左侧或右侧的字符）。这意味着你例子中间的[^e]将变成类似于[^den]。然后，你还必须在模式的开头和结尾添加表达式。这将让你得到像这样的东西（针对你的例子）：[^emn]*d[^mn]*e[^dn]*m[^den]*m[^de]*n[^dem]*。 - raymi

这是正确的，但我想我真正想建议的是，在尝试使用自己的技术之前，将问题委托给类库已经存在的设施。 - Adrian Regan

如果可能的话，将问题委托给现有的软件部件肯定是一个好主意。但是在谈论正则表达式时，永远不要忘记Jamie Zawinski所说的：“有些人面对问题时会想：‘我知道了，我会使用正则表达式。’现在他们有两个问题了。” - raymi

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

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

- raymi · Accepted Answer

我认为这很简单。遍历模式，并对于每个字符在字符串中获取其最后出现位置的索引。索引必须始终增加，否则返回false。因此，伪代码如下：

index = -1
foreach c in pattern
    checkindex = string.lastIndexOf(c)
    if checkindex == -1                   //not found
        return false
    if checkindex < index
        return false
    if string.firstIndexOf(c) < index     //characters in the wrong order
        return false
    index = checkindex
return true

编辑：你可以通过将index作为lastIndexOf方法的起始索引来进一步改进代码。那么，您就不必将checkindex与index进行比较，算法将更快。

更新：修复了算法中的一个错误。添加了额外条件以考虑模式中字母的顺序。