คำอธิบายปัญหา
ในปัญหานี้ เราได้รับอาร์เรย์ของสตริงในรูปแบบ camelCase และ pattern (รูปแบบ) เราต้องพิมพ์สตริงทั้งหมดในอาร์เรย์ที่ตรงกับ pattern ที่กำหนด
อาร์เรย์ของสตริง (Array of strings) คืออาร์เรย์ที่องค์ประกอบเป็นชนิดข้อมูล string
camelCase เป็นวิธีการตั้งชื่อที่พบบ่อยในการเขียนโปรแกรม โดยตัวอักษรแรกของคำใหม่จะขึ้นต้นด้วยตัวพิมพ์ใหญ่ (uppercase) ส่วนที่เหลือเป็นตัวพิมพ์เล็ก
ตัวอย่าง – iLoveProgramming
ปัญหา – หาสตริงทั้งหมดที่ตรงกับ pattern ที่กำหนด
ตัวอย่าง –
Input : "TutorialsPoint" , "ProgrammersPoint" , "ProgrammingLover" , "Tutorials". Pattern : 'P' Output : "TutorialsPoint" , "ProgrammersPoint" , "ProgrammingLover"
คำอธิบาย – เราพิจารณาสตริงทั้งหมดที่มี 'P' อยู่ในนั้น
เพื่อแก้ปัญหานี้ เราจะเพิ่ม keys ทั้งหมดของ dictionary เข้าไปในต้นไม้ (tree) และใช้ตัวอักษรพิมพ์ใหญ่ (uppercase characters) ประมวลผลคำในต้นไม้และพิมพ์คำทั้งหมดที่ตรงกับ pattern
ตัวอย่างโค้ด
#include <bits/stdc++.h> using namespace std; struct TreeNode{ TreeNode* children[26]; bool isLeaf; list<string> word; }; TreeNode* getNewTreeNode(void){ TreeNode* pNode = new TreeNode; if (pNode){ pNode->isLeaf = false; for (int i = 0; i < 26; i++) pNode->children[i] = NULL; } return pNode; } void insert(TreeNode* root, string word){ int index; TreeNode* pCrawl = root; for (int level = 0; level < word.length(); level++){ if (islower(word[level])) continue; index = int(word[level]) - 'A'; if (!pCrawl->children[index]) pCrawl->children[index] = getNewTreeNode(); pCrawl = pCrawl->children[index]; } pCrawl->isLeaf = true; (pCrawl->word).push_back(word); } void printAllWords(TreeNode* root){ if (root->isLeaf){ for(string str : root->word) cout << str << endl; } for (int i = 0; i < 26; i++){ TreeNode* child = root->children[i]; if (child) printAllWords(child); } } bool search(TreeNode* root, string pattern){ int index; TreeNode* pCrawl = root; for (int level = 0; level <pattern.length(); level++) { index = int(pattern[level]) - 'A'; if (!pCrawl->children[index]) return false; pCrawl = pCrawl->children[index]; } printAllWords(pCrawl); return true; } void findAllMatch(vector<string> dictionary, string pattern){ TreeNode* root = getNewTreeNode(); for (string word : dictionary) insert(root, word); if (!search(root, pattern)) cout << "No match found"; } int main(){ vector<string> dictionary = { "Tutorial" , "TP" , "TutorialsPoint" , "LearnersPoint", "TutorialsPointsPrograming" , "programmingTutorial"}; string pattern = "TP"; findAllMatch(dictionary, pattern); return 0; }ผลลัพธ์
TP TutorialsPoint TutorialsPointsPrograming
