資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究連結串列中最長公共字首
連結串列中最長公共字首問題是計算機科學中一個眾所周知的問題，在處理字串或列表時經常遇到。它涉及確定具有最長公共字首的字串或列表元素。
在處理連結串列時，可以採取多種方法。一種常見的方法是遍歷連結串列並比較列表中每個節點的字元，直到找到不匹配為止。直到不匹配點之前的最長公共字首被認為是最長公共字首。
連結串列
線性連結串列可以定義為一個包含可變數量資料項的集合。連結串列的一個元素必須至少包含兩個欄位，一個用於儲存資料，另一個用於儲存下一個元素的地址。連結串列的第二個欄位必須是指標型別。每個這樣的元素被稱為一個節點，因此連結串列可以定義為節點的集合。
與連結串列相關的一些操作包括：
建立
插入
刪除
遍歷
搜尋
連線
顯示
連結串列中最長公共字首演算法
以下演算法將幫助您發現連結串列中最長公共字首：
步驟 1 - 遍歷連結串列，比較每個節點的字元，查詢不匹配或在列表結束時停止。
步驟 2 - 如果在列表結束之前發現不匹配，則直到前一個節點之前的那個字首被認為是最長公共字首。
步驟 3 - 如果沒有發現不匹配並且到達列表的末尾，則跨越整個列表的最長字首是最長公共字首。
在此實現中，函式“最長公共字首”以連結串列的頭作為輸入，並將最長公共字首作為字串返回。為了返回空字串，函式首先確定連結串列是否為空。如果不是，則將字首初始化為頭節點的值，並且從第二個節點開始遍歷列表。該函式對每個節點進行字首值比較，從字首中刪除字元，直到發現不匹配。如果字首曾經變為空，則該函式返回空字串。最後，該函式返回最後一個字首作為最長公共字首。
連結串列中最長公共字首的語法
查詢字串連結串列中最長公共字首的“最長公共字首”函式的語法：
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
int z = INT_MAX;
if(strs.size()==0) return "";
string c = strs[0];
for(int p=1; p<strs.size(); p++){
int q=0,r=0,result=0;
while(q<c.size() && r<strs[p].size()){
if(c[q] == strs[p][r]) result++;
else break;
q++; r++;
}
z = min(result,z);
}
return c.substr(0,z);
}
};
在這種情況下，連結串列中節點的結構稱為“列表節點”，它包含一個字串值和一個指向其後節點的指標。該函式接收對連結串列頭的引用作為輸入，並輸出一個包含連結串列中最長公共字首的字串。
根據具體情況的具體需求，該函式的實現可能會有所不同，但總的來說，它是透過迭代遍歷連結串列並比較每個字串的字元直到找到最長公共字首來實現的。
遵循的方法
方法 1
在上面的程式碼中，首先檢查連結串列是否為空。如果為空，則由於不存在公共字首，因此我們返回空字串。
然後將字首初始化為列表的第一個字串。然後從第二個元素開始，我們向下遍歷列表並將每個字串與字首進行比較。
當前綴和當前字串之間存在差異時，我們跟蹤出錯的第一個字元的索引。然後將字首更新為直到該索引的子字串。
最後返回最長公共字首。如前所述，示例程式碼的輸出將是最長公共字首：fl。
示例 1
#include <iostream>
#include <string>
using namespace std;
struct Listnode {
string value;
Listnode* next;
Listnode(string x) : value(x), next(0) {}
};
string Longestcommonprefix(Listnode* head) {
if (head == nullptr) {
return "";
}
string prefix = head->value;
Listnode* current = head->next;
while (current != nullptr) {
string str = current->value;
int i = 0;
while (i < prefix.length() && i < str.length() && prefix[i] == str[i]) {
i++;
}
prefix = prefix.substr(0, i);
current = current->next;
}
return prefix;
}
int main() {
Listnode* head = new Listnode("flower");
head->next = new Listnode("flow");
head->next->next = new Listnode("flight");
string result = Longestcommonprefix(head);
cout << "Longest common prefix: " << result << endl;
return 0;
}
輸出
Longest common prefix: fl
方法 2
在此示例中，建立了一個字串連結串列（“apple”，“appreciate”，“apex”和“application”）。然後，我們使用連結串列的頭執行 Longestcommonprefix 函式，並將結果儲存在 prefix 變數中。
最後，我們清理用於連結串列的記憶體並將結果（“app”）顯示到控制檯。
示例 2
#include <iostream>
using namespace std;
struct Listnode {
string value;
Listnode* next;
Listnode(string x) : value(x), next(nullptr) {}
};
string Longestcommonprefix(Listnode* head) {
if (!head) {
return "";
}
Listnode* current = head;
string prefix = current->value;
while (current) {
string str = current->value;
int i = 0;
while (i < prefix.length() && i < str.length() && prefix[i] == str[i]) {
i++;
}
prefix = prefix.substr(0, i);
if (prefix.empty()) {
return "";
}
current = current->next;
}
return prefix;
}
int main() {
Listnode* head = new Listnode("apple");
head->next = new Listnode("appreciate");
head->next->next = new Listnode("apex");
head->next->next->next = new Listnode("application");
string prefix = Longestcommonprefix(head);
cout << "The longest common prefix is: " << prefix << endl;
while (head) {
Listnode* temp = head;
head = head->next;
delete temp;
}
return 0;
}
輸出
The longest common prefix is: ap
優點
連結串列中最長公共字首具有多種優點：
效率 - 在連結串列中，其中 n 是節點的數量，可以線上性時間 O(n) 內找到最長公共字首。與其他複雜度更高的技術相比，此技術在確定最長公共字首方面非常有效。
最長公共字首可用於檢查和操作節點中給出的資料。它可用於對類似的物件進行分組或匹配模式等。
可用於最佳化搜尋 - 在大型資料集（例如大型文字檔案）中搜索特定字串時，可以使用最長公共字首來減少需要檢視的字串數量，從而使搜尋更高效。
簡化字串比較 - 由於最長公共字首是兩個字串共有的部分，因此它可用於比較不同的字串。
簡化編碼 - 最長公共字首演算法的實現只需要幾行程式碼，這使得它易於整合到更大的專案或程式碼庫中。
缺點
字首匹配 - 這是最長公共字首演算法的唯一用途。它只能用於確定連結串列中字串的最長公共字首。例如，它不能用於確定最長公共字尾。
難以處理邊緣情況 - 當連結串列只有一個節點或包含具有極短字串的節點時，該技術可能在查詢最長公共字首方面不太成功。
不適合某些型別的資料結構 - 連結串列和字串陣列是最適合最長公共字首技術的。對於其他具有更復雜拓撲結構的資料結構（例如樹或圖），它可能不是最佳策略。
大小寫敏感 - 該演算法區分大小寫，因此它不會將“apple”和“Apple”識別為具有相同的字首。這在某些情況下可能會造成問題。
額外空間 - 如果記憶體有限，那麼演算法需要額外空間來儲存字首字串並進行字串比較可能會成為問題。
結論
總之，最長公共字首演算法是查詢連結串列中字串的最長公共字首的一個好工具。由於其效率，它非常適合處理大型資料集，並且有多種用途，例如字串比較、資料操作和搜尋引擎最佳化。
與大多數演算法一樣，它也有一些缺點，例如無法處理邊緣情況以及僅限於字首匹配。該演算法也區分大小寫，這在某些情況下可能是一個問題。儘管存在這些缺點，但最長公共字首演算法的優點使其成為程式設計師在處理字串連結串列時應該掌握的有價值的工具。
324 次瀏覽
