檢查給定句子中出現的單詞是否基於給定的模式

---

在這個問題中，我們需要檢查字串是否遵循給定的模式。我們可以透過將每個字元對映到單詞來解決這個問題。如果模式的任何字元對映到多個單詞，我們可以說字串不遵循該模式。

問題陳述 – 我們給定一個包含 N 個字元的 'pat' 字串和一個包含 N 個單詞的 'alpha' 字串。給定的任務是檢查 'alpha' 字串是否遵循 'pat' 字串的模式。

注意 – 當單詞按順序與 'pat' 的字元匹配時，我們可以說 'alpha' 字串遵循該模式。

示例

輸入

pat = "ana", alpha = "Hello hi Hello";

輸出

‘Yes’

解釋 – 給定的字串遵循該模式，因為 a -> ‘Hello’，b -> ‘hi’。

輸入

pat = "aba"; alpha = "Welcome to Tutorialspoint!";

輸出

‘No’

解釋 – 讓我們看看字元與字串單詞的對映。

• a -> ‘Welcome’

• b -> ‘to’

• a -> ‘Tutorialspoint’

這裡，'a' 對映到多個單詞，所以我們可以說字串不遵循該模式。

輸入

pat = "bbb"; alpha = "orange orange orange";

輸出

‘Yes’

解釋 – 字串遵循該模式

方法 1

在這種方法中，我們需要找到 'pat' 和 'alpha' 字串遵循的模式。之後，我們可以比較這兩個模式，並確保 'pat' 和 'alpha' 字串的模式是否匹配。

演算法

步驟 1 – 初始化 'words' 對映以將數值對映到字串單詞，'charPointer' 指向字串字元，'tempStr' 儲存單詞，'str' 儲存字串中的單詞模式。

步驟 2 – 開始遍歷 'alpha' 字串。

步驟 3 – 如果當前字元是空格，則執行以下步驟。否則，將字元追加到 'tempStr' 字串。

步驟 4 – 如果 'tempStr' 字串不為空並且在對映中不存在，則在將其遞增 1 後，將 'tempStr' 和 'charPointer' 值插入到對映中。

步驟 5 – 如果 'tempStr' 存在於對映中，則取對映的數值並將相關的字元值追加到 'str' 字串。

步驟 6 – 同時，用空字串重新初始化 'tempStr'。

步驟 7 – 完成迭代後處理字串的最後一個單詞。

步驟 8 – 初始化 'patternMap' 對映以儲存 'pat' 字串字元的模式，'final_pat' 儲存模式。

步驟 9 – 迭代 'pat' 字串。如果字串字元在對映中不存在，則使用 'charPointer' 值插入該字元。

步驟 10 – 接下來，從對映中獲取與字元相關的對映值，並將其追加到 'final_pat' 字串。

步驟 11 – 最後，如果 final_pat 和 str 字串匹配，則返回 true。否則，返回 false。

示例

#include <bits/stdc++.h>
using namespace std;

bool isPatternExists(string pat, string alpha) {
    // To store words of the string
    map<string, int> words;
    int charPointer = -1;
    string tempStr = "";
    string str = "";
    // Start traversing the string
    for (int a = 0; a < alpha.length(); a++) {
        // If we get the space, the word is completed
        if (alpha[a] == ' ') {
            // If a word does not exist in the map, add it
            if (!tempStr.empty() && words.find(tempStr) == words.end()) {
                words.insert({tempStr, ++charPointer});
            }
            if (words.find(tempStr) != words.end()) {
                // If word exists
                str += ((char)((words.find(tempStr))->second + 'a'));
            }
            // Re-initialization
            tempStr = "";
        } else {
            // Get word
            tempStr += alpha[a];
        }
    }
    // Handling the last word
    if (!tempStr.empty() && words.find(tempStr) == words.end())
        words.insert({tempStr, ++charPointer});
    if (words.find(tempStr) != words.end())
        str += ((char)((words.find(tempStr))->second + 'a'));
    map<char, int> patternMap;
    charPointer = -1;
    string final_pat = "";
    // Create the mapping for the pattern
    for (int a = 0; a < pat.length(); a++) {
        // Insert char to map
        if (patternMap.find(pat[a]) == patternMap.end())
            patternMap.insert({pat[a], ++charPointer});
        // If character already exists
        if (patternMap.find(pat[a]) != patternMap.end())
            final_pat += ((char)((patternMap.find(pat[a]))->second + 'a'));
    }
    return final_pat == str;
}
int main() {
    string pat = "ana";
    string alpha = "Hello hi Hello";
    if (isPatternExists(pat, alpha)) {
        cout << "The string follows the given pattern";
    } else {
        cout << "The string does not follow the given pattern";
    }
    return 0;
}

輸出

The string follows the given pattern

時間複雜度 – O(NlogN)，因為我們在對映中搜索。

空間複雜度 – O(N)，因為我們使用對映資料結構。

在解決方案中，我們建立並匹配了兩個字串的通用模式。但是，程式設計師可以不建立通用模式來解決問題，但需要交叉檢查單個字元不應對映到不同的單詞，單個單詞不應對映到不同的字元。