java - 文本查询匹配(棘手)

Question

我在大学参加了微软编码挑战，提出的问题是:

Write a program that takes two strings as input, one is a query, and the other is a string that may or may not contain that query. Your program needs to find if the query is contained within the body string.

1) The query should only match the body text if it matches the start of a word within the body text.

2) That is, the beginning of the query must also be the start of a word within the body text. For example, the query "cat" would match the strings "cat", "cat toy", "this is a cat", and "catty". However, the query "cat" would not match the string "location".

3) Your program should be case insensitive.

4) Your program needs to be able to match queries without spaces in them, even if the body does have spaces. For example, the string "Luke Johnston" would be matched by the query "luke j" and the query "lukej".

5) However, this does not work the other way around. The query "luke j" should not match the string "lukejohnston".

我能够编写满足前 4 个要求的代码，但我无法找到第 5 个要求的解决方案。任何提示/帮助表示赞赏。这是我的代码版本。

package regex;

import java.util.Scanner;

public class TextQueryMatch {
public static void main(String[] args){
    Scanner in = new Scanner(System.in);
    System.out.print("Enter the Text: ");
    String text = in.nextLine();
    text = text.toLowerCase();
    String[] substexts = text.split("\\s");
    text = "";
    for(int i = 0; i < substexts.length; i++){
        char capLetter = Character.toUpperCase(substexts[i].charAt(0));
        text += capLetter + substexts[i].substring(1, substexts[i].length());
    }
    System.out.println(text);
    System.out.print("Enter the Query: ");
    String query = in.nextLine();
    query = query.toLowerCase();
    String[] subquerys = query.split("\\s");
    query = "";
    for(int i = 0; i < subquerys.length; i++){
        char capLetter = Character.toUpperCase(subquerys[i].charAt(0));
        query += capLetter + subquerys[i].substring(1, subquerys[i].length());
    }
    System.out.println(query);
    System.out.print("Match: ");
    if(text.matches("(.*)"+query.charAt(0)+"(.*)")){
        text=text.toLowerCase();
        query=query.toLowerCase();
        System.out.print(text.matches("(.*)"+query+"(.*)"));
    }else{
        System.out.print("False");
    }
}
}

Answer 1

我认为将查询转换为正则表达式就足以满足所有给定的条件。

根据问题，

根据第 1 点和第 2 点，仅当查询字符串位于文本开头或空格后面时，查询才应与文本匹配。所以基本上这个正则表达式会是这样的 -

(^|\s)(query-string)

第3点需要查询不区分大小写，这可以在编译查询正则表达式时处理。

对于第 4 点和第 5 点 - 即使查询没有空格，查询也应该与文本匹配，但如果查询中存在空格，则它应该在文本中正确匹配。

因此，我们需要以这样的方式转换我们的正则表达式，即在每个字符(或空格)之后，正则表达式可以处理可能存在或可能不存在的空格。这样，我们假设字符(或空格) ) 必须匹配，而其后面的空格是有条件的。

这应该有效 -

 public static boolean find_match(String query, String text){
    String regex = "(?:^|\\s)(" + query.replaceAll(".(?!$)", "$0(?:\\\\s*)") + ")";
    //System.out.println("Regex -> " + regex);
    Pattern re = Pattern.compile(regex, Pattern.CASE_INSENSITIVE);    
    return re.matcher(text).find();
 }

测试此功能 -

public static void main(String []args){        
    String query1 = "cat";
    String[] text1 = {
        "Cat",
        "caT toy",
        "This is a CaT",
        "caTty",
        "loCation"
    };
    for(String s : text1){
        System.out.println("Query -> " + query1 + "\nText -> " + s + "\n" + find_match(query1, s) + "\n");
    }
    String query2 = "luke j";
    String query3 = "lukej";
    String[] text2 = {
        "Luke Johnson",
        "lukejohnson",
        "Luke      Johson",
        "This is Luke  Johnson",
        "L ukeJohnson",
        "L uke Johnson"
    };
    for(String s : text2){
        System.out.println("Query -> " + query2 + "\nText -> " + s + "\n" + find_match(query2, s));
        System.out.println("Query -> " + query3 + "\nText -> " + s + "\n" + find_match(query3, s) + "\n");
    }    
 }

输出 ->

Query -> cat
Text -> Cat
true

Query -> cat
Text -> caT toy
true

Query -> cat
Text -> This is a CaT
true

Query -> cat
Text -> caTty
true

Query -> cat
Text -> loCation
false

Query -> luke j
Text -> Luke Johnson
true
Query -> lukej
Text -> Luke Johnson
true

Query -> luke j
Text -> lukejohnson
false
Query -> lukej
Text -> lukejohnson
true

Query -> luke j
Text -> Luke      Johson
true
Query -> lukej
Text -> Luke      Johson
true

Query -> luke j
Text -> This is Luke  Johnson
true
Query -> lukej
Text -> This is Luke  Johnson
true

Query -> luke j
Text -> L ukeJohnson
false
Query -> lukej
Text -> L ukeJohnson
true

Query -> luke j
Text -> L uke Johnson
true
Query -> lukej
Text -> L uke Johnson
true

希望这有帮助 -