檢查給定字串是否可以使用矩陣相鄰單元格的字元構成


讓我們首先了解矩陣中相鄰單元格的含義。為了確定每個元件如何在您的二維矩陣結構中擬合,請將每個封閉單元視覺化為被幾乎八個相鄰元素包圍,這些元素位於它們周圍/來自它們的對角方向以及垂直/水平方向。關於晶格大小可以進行一個示例觀察 - 此設計中最小的圓形封閉體包含九個元件。(從左到右和從上到下)單元格 [行=9,列=8] - 在 [行=8,列=7] 的範圍內,…[行=10,列=8],等等。這個複雜的連線網路連線了這些相鄰的元件,它們共享邊或角;建立了一個定義良好的矩陣結構,提高了其執行各種操作和計算的能力。

方法

  • 迭代方法

  • 迭代方法 II

迭代方法

迭代方法是一種解決問題的策略,它涉及執行迴圈或迭代。例如,此技術可用於確定是否可以從相鄰矩陣單元格中的字元建立特定字串。

通常,問題陳述包括目標字串和字元矩陣。目標是確定是否可以透過在相鄰矩陣單元格之間向上、向下、向左或向右移動來生成目標字串。

語法

確定是否可以使用相鄰矩陣單元格中的字元建立字串的語法,假設矩陣表示為二維陣列,並且給定字串儲存在名為 input String 的變數中。

  • 將布林函式 string Found 設定為 false。

  • 使用兩個巢狀迴圈遍歷矩陣中的所有單元格。

  • 對於每個單元格,檢查 input string 中當前字元是否與矩陣的當前單元格匹配。

  • 如果找到匹配項,則遞迴檢查是否可以使用當前單元格在矩陣中的相鄰單元格生成 input string 中剩餘的字元。

  • 如果可以使用附近的矩陣單元格生成完整的 input string,則將 string Found 變數更改為 true 並退出迴圈。

  • 完成此迴圈後,如果可以使用矩陣的相鄰單元格生成 input string,則 string Found 返回 true,否則返回 false。

演算法

  • 步驟 1 - 將布林變數“found”的值更改為 false。

  • 步驟 2 - 單獨檢視每個矩陣單元格。

  • 步驟 3 - 如果所需字串的第一個字元與當前單元格匹配,我們使用當前單元格的點和字串中下一個字元的索引來執行遞迴函式“search”。

  • 步驟 4 - 在返回之前,如果“search”函式的索引等於所需字串的長度,則必須將“found”變數設定為 true。

  • 步驟 5 - 我們透過迴圈遍歷它們來檢查相鄰單元格中的字元。如果其中任何一個與字串的下一個字元匹配,則使用更高的索引和新的座標再次執行“search”方法。

  • 步驟 6 - 如果沒有相鄰單元格與字串中的下一個字元匹配,則退出函式。

示例 1

can_form_string 方法迭代地確定是否可以從指定的單元格 (i,j) 開始使用相鄰矩陣單元格生成提供的字串。如果可以使用相鄰單元格建立整個字串,則返回 true;否則,返回 false。

要測試的字串被硬編碼為“abcfi”,並且在主函式中為矩陣中的每個單元格呼叫 can_form_string 函式。如果找到匹配項,則應用程式會生成一條訊息,指示可以使用相鄰矩陣單元格構造該字串。如果無法使用相鄰矩陣單元格建立該字串,則會生成一條此類訊息。

#include <iostream>
#include <cstring>
using namespace std;

const int N = 3; 
char matrix[N][N] = {
   {'a', 'b', 'c'},
   {'d', 'e', 'f'},
   {'g', 'h', 'i'}
}; 

bool can_form_string(int i, int j, const char* str) {
   if (*str == '\0') {
      return true; 
   }
   if (i < 0 || i >= N || j < 0 || j >= N) {
      return false; 
   }
   if (matrix[i][j] != *str) {
      return false; 
   }
   const char* rest_of_str = str + 1; 
   return (
      can_form_string(i-1, j, rest_of_str) || 
      can_form_string(i+1, j, rest_of_str) || 
      can_form_string(i, j-1, rest_of_str) || 
      can_form_string(i, j+1, rest_of_str)    
   );
}
int main() {
   const char* str_to_check = "abcfi";
   bool result = false;
   for (int i = 0; i < N; i++) {
      for (int j = 0; j < N; j++) {
         result = can_form_string(i, j, str_to_check);
         if (result) {
            break; 
         }
      }
      if (result) {
         break; 
      }
   }
if (result) {
   cout << "The string "" << str_to_check << "" can be formed using adjacent cells of the matrix." << endl;
   } else {
      cout << "The string "" << str_to_check << "" cannot be formed using adjacent cells of the matrix." << endl;
   }
   return 0;
}

輸出

The string  << str_to_check <<  can be formed using adjacent cells of the matrix.

演算法

以下是將此策略付諸實踐的步驟 -

  • 步驟 1 - 從左上角開始導航矩陣,查詢與當前單元格對應的字串的第一個字元。

  • 步驟 2 - 如果匹配,則將當前單元格標記為已訪問並轉到字串的下一個字元。

  • 步驟 3 - 如果不匹配,我們繼續下一個單元格並再次重複步驟 2。

  • 步驟 4 - 如果我們在任何時候都無法找到字串中下一個字元的匹配項,則返回到上一個位置並嘗試另一個相鄰單元格。

  • 步驟 5 - 如果我們能夠匹配字串中的所有字元併到達字串的末尾,則返回 true。否則返回 false。

示例 2

此應用程式中的 canFormString() 函式迭代地確定是否可以從相鄰矩陣單元格的字元中構成提供的字串。

該過程接收一個字串、一個矩陣、字串中當前字元的索引、當前行和列索引、一個用於已訪問單元格的監控矩陣以及一個已訪問單元格索引的矩陣。如果函式成功建立了字串,則返回 true;如果它無效,則返回 false。

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

bool canFormString(vector<vector<char>>& matrix, string s, int i, int j, int k,
vector<vector<bool>>& visited) {

   if (k == s.length())
   return true;

   if (i < 0 || j < 0 || i >= matrix.size() || j >= matrix[0].size() ||
   visited[i][j] || matrix[i][j] != s[k])
   return false;
   visited[i][j] = true;


   bool canForm = canFormString(matrix, s, i - 1, j - 1, k + 1, visited) ||
   canFormString(matrix, s, i - 1, j, k + 1, visited) ||
   canFormString(matrix, s, i - 1, j + 1, k + 1, visited) ||
   canFormString(matrix, s, i, j - 1, k + 1, visited) ||
   canFormString(matrix, s, i, j + 1, k + 1, visited) ||
   canFormString(matrix, s, i + 1, j - 1, k + 1, visited) ||
   canFormString(matrix, s, i + 1, j, k + 1, visited) ||
   canFormString(matrix, s, i + 1, j + 1, k + 1, visited);

   visited[i][j] = false;

   return canForm;
}

int main() {
   vector<vector<char>> matrix{{'A', 'C', 'P'},
   {'A', 'O', 'E'},
   {'G', 'B', 'L'}};


   string s1 = "APPLE";
   string s2 = "BALL";
   string s3 = "GOOGLE";


   vector<vector<bool>> visited(matrix.size(), vector<bool>(matrix[0].size(), false));

   cout << s1 << " can " << (canFormString(matrix, s1, 0, 0, 0, visited) ? "" : "not ") << "be formed\n";
   cout << s2 << " can " << (canFormString(matrix, s2, 0, 0, 0, visited) ? "" : "not ") << "be formed\n";
   cout << s3 << " can " << (canFormString(matrix, s3, 0, 0, 0, visited) ? "" : "not ") << "be formed\n";

   return 0;
}

輸出

APPLE can not be formed
BALL can not be formed
GOOGLE can not be formed

結論

要檢視是否可以使用矩陣的相鄰單元格中的字元建立給定字串,我們必須首先找到每個元素的相鄰單元格。一旦我們找到了相鄰單元格,我們就可以檢查字串中的字元是否與矩陣中每個元素的相鄰單元格中的字元匹配。

此方法廣泛用於諸如單詞搜尋謎題或自然語言處理任務之類的應用程式中,在這些應用程式中,我們需要確定是否可以使用矩陣或網格中相鄰的字母構造給定的單詞。如果我們理解矩陣中相鄰單元格的概念,我們可以有效地解決這些型別的問題和任務。

更新於: 2023年7月31日

137 次檢視

開啟您的 職業生涯

透過完成課程獲得認證

立即開始
廣告