8

我不知道如何解决这个问题：

给定两个字符串，一个代表一个模式，一个是随机字符串，确定它是否与第一个字符串匹配

前任：

string1: "aaba"
string2: "catcatdogcat"

因此，string1 和 string2 是模式匹配的

与如果 string2 是"catcatcatcat"这将不是模式匹配的。

对任何模式和字符串执行此操作。

我知道这是递归，但我很坚持......如何解决这个问题

4

3 回答 3

2

取唯一字母的数量。然后，您想使用以下约束遍历每个字母的所有可能长度组合：

  1. sum(字母长度 * 字母出现次数) 必须是 string2 的长度
  2. 每个长度必须至少为 1

也就是说，对于 2 个唯一字母和 4 个字符串长度，可能的长度为：

(1, 3) 和 (2, 2)

从这里开始很简单。对于每个唯一字母，您可以找出该字母必须代表给定字符串的字符串，因为您知道每个字母的长度。然后将每个字母映射到它必须表示的字符串，如果在任何时候一个字母对应的字符串不匹配它的早期实例，那么你没有匹配。

对于您的示例：

string1: "aaba"
string2: "catcatdogcat"

这里，对于长度为 (3, 3) 的迭代。因为我们知道 a 的长度为 3，所以我们知道 a 的第一次迭代必须是“cat”。然后下一个a，对应“cat”（还是有匹配的）。那么接下来的3个必须对应于b。这是第一个 b 所以它可以匹配任何 3 个字符。然后将最后的 a 再次匹配到 cat ，你就完成了。

如果您希望 a,b,c 如@MartijnCourteaux 评论中所述是唯一的（现在我再次阅读了您的问题），那么最后您可以检查您的地图是否有共同值，如果有任何共同值然后你没有对手。

如果您在任何迭代中都有匹配项，则字符串与模式匹配。如果在所有迭代中都没有匹配，则只有没有匹配。

于 2013-10-22T19:18:30.093 回答
2

好的，我将尝试为此解释递归，听起来不错，但我没有机会测试它（不在家里）。

取一个向量 v['size of alphabet']，其中 v[i] = string2 中的多少个字母 = string 1 中的字母 i。

在你的情况下，它最终是： v['a'] = 3, v[b] =3;

用 1 初始化向量。

对于 rec 函数：

您从 string1 中获取第一个字母： a; 代表 a from string2 是从 string2 开始到 string2+v['a'] 结束的字符串；这是'c'；您检查这是否是一个有效的解决方案，直到现在，它是。

然后你进入rec(string1 + 1)，再次输入a，因为v['a']仍然= 1，那么你将第二个a作为='a'。您检查这是否是一个有效的解决方案，这不是因为您已经将第一个 a 定义为“c”。你回到递归并增加 v['a']，从乞求开始。

你取 string1 的第一个字母：a; 从 string2 代表 'ca' ，（现在 v['a'] = 2 ）检查是否有效。记录（字符串1 +1）；

依此类推...在某个点上，您将达到 v['a'] = 3 和 v['b'] = 3; 然后使用 rec 功能，您将找到解决方案。

我发现在交互函数中实现起来更容易，但是你说了一些关于递归的事情，所以是的。

于 2013-10-22T18:49:44.083 回答
1

这很容易实现：

正则表达式是要走的路。在正则表达式中，有一种叫做反向引用的东西。反向引用需要匹配相同的字符串，提到的匹配组已经匹配。即正则表达式^([ab])\\1$将匹配每个字符串，如aaor bb。第一组匹配 a 或 b - 但反向引用需要匹配相同的东西，匹配组（在本例中为“1”）匹配。

因此，您需要做的就是：将您的基于字符串的模式转换为正则表达式模式。

例子：

String regex = "^([a-z]+)\\1([a-z]+)\\1$";
   Pattern p = Pattern.compile(regex);
   Matcher m = p.matcher("catcatdogcat");

   if (m.matches()){
     System.out.println("matches!");
     System.out.println(m.group(0));
     System.out.println(m.group(1));
     System.out.println(m.group(2));

   }else{
    System.out.println("no matches!");
   }

产生：

matches!
catcatdogcat
cat
dog

这将完全匹配您给定的字符串“catcatdogcat”，同时匹配第 1 组蜜蜂“猫”和第 2 组蜜蜂“狗”。

你现在需要做的是：

  • aaba编写一个函数，逐个字符地检查您的字符串模式。
  • 首次出现的字母：将其替换为([a-z]+)并记下该匹配组的编号（Array、Hashmap、...）
  • 该字母的任何进一步出现：将其替换为\\1（如果该字母的记录编号为 1）
  • ^用和包装结果$。

最后，您的 Stringaaba将被转换^([a-z]+)\\1([a-z]+)\\1$为您的需求并满足您的需求。该模式abccba将成为正则表达式^([a-z]+)([a-z]+)([a-z]+)\\3\\2\\1$

最后使用匹配器来检查你给定的字符串。

此示例仅假定小写字符，但您可以对其进行扩展。

但是保留“+”很重要，因为“*”将允许零长度匹配，这将使您的正则表达式始终匹配。

提到的第二个例子：

import java.util.regex.*;

public class HelloWorld {
  public static void main(String[] args) {
   String regex = "^([a-z]+)([a-z]+)([a-z]+)\\3\\2\\1$";
   Pattern p = Pattern.compile(regex);
   Matcher m = p.matcher("catdogcowcowdogcat");

   if (m.matches()){
     System.out.println("matches!");
     System.out.println(m.group(0));
     System.out.println(m.group(1));
     System.out.println(m.group(2));
     System.out.println(m.group(3));

   }else{
    System.out.println("no matches!");
   }
  }
}

产生：

matches!
catdogcowcowdogcat
cat
dog
cow

编辑：如果需要（即使它不是 100% 符合您的要求 - 请参阅评论）：

public static String convertToRegex(String pattern){
    String regex = "";
    Map<Character, Integer> refs = new HashMap<Character, Integer>();
    Integer i=1;
    for (Character c : pattern.toCharArray()){
      if (refs.containsKey(c)){
         //known.
         regex += "\\" + refs.get(c);
      }else{
         //unknown
         regex += "([a-z]+)";
         refs.put(c, i++);
      }
    }

    return "^" + regex + "$";
  }
于 2013-10-22T19:44:27.227 回答