Word Squares ใน C ++

สมมติว่าเรามีชุดคำ (ทั้งหมดไม่ซ้ำกัน) เราต้องหาช่องคำศัพท์ทั้งหมดและเราสามารถสร้างจากคำเหล่านั้นได้ ในที่นี้ ลำดับของคำจะสร้างช่องสี่เหลี่ยมคำที่ถูกต้อง ถ้าแถวและคอลัมน์ที่ k อ่านสตริงเดียวกันทุกประการ โดยที่ 0 ≤ k <สูงสุดของ numRows และ numColumns ตัวอย่างเช่น ลำดับคำ ["ball","area","lead","lady"] จะสร้างช่องคำศัพท์ขึ้นเนื่องจากแต่ละคำอ่านเหมือนกันทั้งในแนวนอนและแนวตั้ง

ดังนั้น หากอินพุตเป็นเหมือน ["area","lead","wall","lady","ball"] เอาต์พุตจะเป็น [[ "wall", "area" , "ตะกั่ว", "ผู้หญิง"], ["บอล", "พื้นที่", "ตะกั่ว", "ผู้หญิง"]]

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดโครงสร้างโหนด โดยจะมีตัวแปร isEnd และรายการโหนดย่อย

• กำหนดอาร์เรย์ 2D ret หนึ่งรายการ

• กำหนดฟังก์ชัน insertNode() นี้จะใช้หัว s,

• โหนด :=หัว

• สำหรับการเริ่มต้น i :=0 เมื่อ i

  • x :=s[i]

  • หากอาร์เรย์ย่อยของโหนดว่างเปล่า −

    • ลูก[x] ของโหนด :=โหนดใหม่

  • โหนด :=ลูก[x] ของโหนด

• isEnd ของโหนด :=จริง

• กำหนดฟังก์ชันที่เรียกว่า getAllWords ซึ่งจะใช้ idx, prefixm node และ temp array

• หากโหนดว่างเปล่า −

  • กลับ

• ถ้า isEnd ของโหนดเป็นจริง −

  • ใส่ curr ที่จุดสิ้นสุดของอุณหภูมิ

  • กลับ

• ถ้า idx>=ขนาดของคำนำหน้า −

  • สำหรับแต่ละโหนดในโหนดย่อย -

    • getAllWords(idx, prefix, it.second, temp, curr + it.first)

• มิฉะนั้น −

  • x :=คำนำหน้า[idx]

  • ถ้าลูกของโหนดไม่ว่างเปล่า −

    • กลับ

  • getAllWords(idx + 1, คำนำหน้า, ลูก[x] ของโหนด, temp, curr + x)

• กำหนดฟังก์ชัน Solve() ซึ่งจะใช้อาร์เรย์ temp, idx, reqSize, head,

• ถ้า idx เหมือนกับ reqSize แล้ว −

  • ใส่ temp ที่ท้าย ret

  • กลับ

• คำนำหน้า :=สตริงว่าง

• สำหรับการเริ่มต้น i :=0 เมื่อ i

  • คำนำหน้า :=คำนำหน้า + อุณหภูมิ[i, idx]

• กำหนดอาร์เรย์ที่เป็นไปได้

• curr =หัว

• getAllWords(0, คำนำหน้า, สกุลเงิน, เป็นไปได้)

• สำหรับการเริ่มต้น i :=0 เมื่อฉัน <ขนาดที่เป็นไปได้ ให้อัปเดต (เพิ่ม i ขึ้น 1) ทำ -

  • s :=เป็นไปได้[i]

  • ใส่ s เมื่อสิ้นสุดอุณหภูมิ

  • แก้ (temp, idx + 1, reqSize, head)

  • ลบองค์ประกอบสุดท้ายออกจาก temp

• จากวิธีหลัก ให้ทำดังต่อไปนี้ −

• หัว =โหนดใหม่

• สำหรับการเริ่มต้น i :=0 เมื่อ i <ขนาดของคำ อัปเดต (เพิ่ม i ขึ้น 1) ทำ -

  • insertNode(หัว, คำ[i])

• กำหนดอุณหภูมิอาร์เรย์

• สำหรับการเริ่มต้น i :=0 เมื่อ i <ขนาดของคำ อัปเดต (เพิ่ม i ขึ้น 1) ทำ -

  • s :=คำ[i]

  • ใส่ s เมื่อสิ้นสุดอุณหภูมิ

  • แก้ (ชั่วคราว 1 ขนาดของคำ[0] หัว)

  • ลบองค์ประกอบสุดท้ายออกจาก temp

• รีเทิร์น

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<vector<auto>> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << "[";
      for(int j = 0; j <v[i].size(); j++){
         cout << v[i][j] << ", ";
      }
      cout << "],";
   }
   cout << "]"<<endl;
}
struct Node {
   bool isEnd;
   map<char, Node *> child;
};
class Solution {
public:
   vector<vector<string>> ret;
   void insertNode(Node *head, string &s) {
      Node *node = head;
      for (int i = 0; i < s.size(); i++) {
         char x = s[i];
         if (!node->child[x]) {
            node->child[x] = new Node();
         }
         node = node->child[x];
      }
      node->isEnd = true;
   }
   void getAllWords(int idx, string prefix, Node *node, vector<string>&temp,
      string curr = "") {
         if (!node)
            return;
         if (node->isEnd) {
            temp.push_back(curr);
            return;
         }
         if (idx >= prefix.size()) {
            for (auto &it : node->child) {
               getAllWords(idx, prefix, it.second, temp, curr + it.first);
            }
         }
         else {
            char x = prefix[idx];
            if (!node->child[x])
               return;
            getAllWords(idx + 1, prefix, node->child[x], temp, curr + x);
         }
   }
   void solve(vector<string> &temp, int idx, int reqSize, Node *head){
      if (idx == reqSize) {
         ret.push_back(temp);
         return;
      }
      string prefix = "";
      for (int i = 0; i < temp.size(); i++) {
         prefix += temp[i][idx];
      }
      vector<string> possible;
      Node *curr = head;
      getAllWords(0, prefix, curr, possible);
      for (int i = 0; i < possible.size(); i++) {
         string s = possible[i];
         temp.push_back(s);
         solve(temp, idx + 1, reqSize, head);
         temp.pop_back();
      }
   }
   vector<vector<string>> wordSquares(vector<string> &words) {
      ret.clear();
      Node *head = new Node();
      for (int i = 0; i < words.size(); i++) {
         insertNode(head, words[i]);
      }
      vector<string> temp;
      for (int i = 0; i < words.size(); i++) {
         string s = words[i];
         temp.push_back(s);
         solve(temp, 1, (int)words[0].size(), head);
         temp.pop_back();
      }
      return ret;
   }
};
main() {
   Solution ob;
   vector<string> v = {"area", "lead", "wall", "lady", "ball"};
   print_vector(ob.wordSquares(v));
}

อินพุต

{"area", "lead", "wall", "lady", "ball"}

ผลลัพธ์

[[wall, area, lead, lady, ],[ball, area, lead, lady, ],]