題目描述

當我們寫一些東西時,很容易就會犯下重複寫出一個單字的錯誤。舉例來說,「Monmoy loves to to code」中的「to」重複了。



使用正規表示式,我們可以簡單地從一個文本中找出重複的樣本。在這個題目中,您將會得到一個文本,您的任務是要找出連續重複的單字,並且將之後重複的單字刪除,只保留最前面的單字。

在這個題目中,相同字母但不同大小寫的單字被當作是同樣的單字。

原題網址

輸入格式

第一行包含一個整數N,為測試資料的數量,範圍在1到100之間(包含1和100)。接下來的N行皆為一個由英文字母和空格組成的字串,每行字串的長度不超過104

輸出格式

輸出去除掉連續重複單字後的結果,記得保留第一個出現的單字。

範例輸入

4
Goodbye bye bye world world world
Swapnil went went to to to his business
Rana is is the the best player in eye eye game
in inthe

範例輸出

Goodbye bye world
Swapnil went to his business
Rana is the best player in eye game
in inthe

解題概念

一個單字的起頭可以是字串的起頭、空格、或是上一個單字與空格的結尾。可以寫成如下正規表示式:

"(\\A|\\s+|\\G)"

單字本身的部份,可以寫成如下正規表示式:

"\\w+"

若這個單字之後還有重複的單字,可以寫成如下正規表示式:

"(\\w+)(\\s+\\1)+"

「\1」用來表示第一個群組所包含的字段。若單字為A,那「A A」、「A A A」、「A A A ... A」都可以符合這個正規表示式。

至於一個單字的結尾可以是字串的結尾或是空格。可以寫成如下正規表示式:

"(\\s+|\\z)"

合併上面的式子,可以得到以下正規表示式:

"((\\A|\\s+|\\G)((\\w+)(\\s+\\4)+)(\\s+|\\z))"

其中,第三個群組為重複的單字字段,第四個群組為重複單字第一次出現的單字字段。所以可以用第四個群組的字串,去取代第三個群組的字串,即可消除重複單字,並保留第一次出現的重複單字。

題目需要忽略英文大小寫,因此可以在產生樣本的時候,加上「Pattern.CASE_INSENSITIVE」旗標,來讓樣本忽略英文大小寫。

參考答案

import java.util.Scanner;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class DuplicateWords {

    public static void main(String[] args) {

        String pattern = "((\\A|\\s+|\\G)((\\w+)(\\s+\\4)+)(\\s+|\\z))";
        Pattern r = Pattern.compile(pattern, Pattern.CASE_INSENSITIVE);

        Scanner in = new Scanner(System.in);
        int testCases = Integer.parseInt(in.nextLine());
        while (testCases > 0) {
            String input = in.nextLine();
            Matcher m = r.matcher(input);
            boolean findMatch = true;
            while (m.find()) {
                input = input.replaceAll(m.group(3), m.group(4));
                findMatch = false;
            }
            System.out.println(input);
            testCases--;
        }
    }
}