刪除序列中連續的相同單詞


難度級別
經常問 事實集
排列 排序

問題陳述

問題“刪除序列中連續的相同單詞”說明您被賦予了一個 的n 字符串。 如果連續出現兩個相同的單詞,請刪除兩個單詞。 刪除所有此類對後,打印列表中剩餘的單詞/字符串總數。

刪除序列中連續的相同單詞

s[ ] = {ab, aa, aa, bcd, ab}
3
s[ ] = {cpp, cpp, java}
1

使用堆棧

算法

  1. 初始化清單 n 字符串.
  2. 創建一個 數據結構。
  3. 從0遍歷到列表的大小– 1。
    1. 檢查堆棧是否為空,即堆棧的大小為0
      1. 將單詞推入/插入堆棧列表中當前索引處。
    2. 否則,將創建一個字符串變量,並將該字符串存儲在堆棧的頂部。
      1. 如果兩個字符串相同,則將字符串變量與列表中當前索引處的單詞進行比較。
        1. 從堆棧頂部刪除字符串。
      2. 否則,如果字符串不同。
        1. 將當前索引處的字符串推入堆棧。
  4. 返回堆棧的大小。

推薦碼

C ++程序刪除序列中連續的相同單詞

#include<bits/stdc++.h> 
using namespace std; 
  
int removeConsSame(vector<string > s){ 
    stack<string> st; 
  
    for(int i=0; i<s.size(); i++){ 
        if(st.empty()){ 
            st.push(s[i]);
        }
        
        else{ 
            string str = st.top(); 
  
            if(str.compare(s[i]) == 0){ 
                st.pop(); 
            }
  
            else{
                st.push(s[i]);
            }
        } 
    } 
  
    return st.size(); 
} 
  
int main(){ 
    vector<string> s = {"ab", "aa", "aa", "bcd", "ab"};
    
    cout << removeConsSame(s); 
    
    return 0; 
}
3

Java程序刪除序列中連續的相同單詞

import java.util.Vector; 
import java.util.Stack; 
  
class removeSame{ 
    
    static int removeConsSame(Vector <String > s){ 
        Stack<String> st = new Stack<>(); 
       
        for(int i=0; i<s.size(); i++){ 
            if(st.empty()){ 
                st.push(s.get(i));
            }
            
            else{ 
                String str = st.peek(); 
       
                if(str.equals(s.get(i))){     
                    st.pop(); 
                }
       
                else{
                    st.push(s.get(i));
                }
            } 
        } 
        return st.size(); 
    } 
      
    public static void main(String[] args){ 
        Vector<String> s = new Vector<>(); 
  
        s.addElement("ab"); 
        s.addElement("aa"); 
        s.addElement("aa");
        s.addElement("bcd");
        s.addElement("ab");
  
        System.out.println(removeConsSame(s)); 
    } 
}
3

複雜度分析

時間複雜度

O(N) 其中n是列表中的字符串數。 正如我們剛剛遍歷字符串一樣,時間複雜度僅為O(n),這使得算法可以在線性時間內運行。 但是要注意的一件事是,正在比較字符串,並且我們已經考慮到字符串具有一些恆定長度,該長度小於N。因為在最壞情況下,字符串比較需要O(length)時間。

空間複雜度

O(N) 因為我們使用空間來存儲n個字符串。n每噹噹前索引處的字符串與堆棧頂部的字符串不同時。 我們將當前索引處的字符串推入堆棧。 在最壞的情況下,我們可能最終會將所有字符串推入堆棧。 這種情況導致O(n)空間複雜性。

不使用堆棧

算法

  1. 初始化清單 n 字符串。
  2. 從0遍歷到列表的大小– 2。
    1. 將列表中當前索引處的單詞與列表中當前索引+1處的單詞進行比較。
      1. 如果兩個字符串都不相同。
        1. 增加當前索引
      2. 否則,如果兩個字符串都相同。
        1. 從列表中刪除/擦除兩個字符串。
        2. 檢查當前索引是否大於0
          1. 減少當前索引。
        3. 將列表的大小更新為列表的大小– 2。
  3. 返回列表的大小。

推薦碼

C ++程序刪除序列中連續的相同單詞

#include<bits/stdc++.h> 
using namespace std; 
  
int removeConsSame(vector <string > s){ 
    int n = s.size(); 
  
    for(int i=0; i<n-1; ){ 
        if(s[i].compare(s[i+1]) == 0){ 
            s.erase(s.begin()+i); 
            s.erase(s.begin()+i); 
  
            if(i > 0){ 
                i--; 
            }
  
            n = n-2; 
        } 
  
        else{
            i++;
        }
    } 
    return s.size(); 
} 
  
int main(){ 
    vector<string> s = {"ab", "aa", "aa", "bcd", "ab"};
    
    cout << removeConsSame(s); 
    
    return 0; 
}
3

Java程序刪除序列中連續的相同單詞

import java.util.Vector; 
  
class removeSame{ 
    
    static int removeConsSame(Vector <String > s){ 
        int n = s.size(); 
       
        for(int i=0; i<n-1; ){ 
            if(s.get(i).equals(s.get(i+1))){ 
                s.remove(i); 
                s.remove(i); 
       
                if(i > 0){ 
                    i--; 
                }
       
                n = n-2; 
            } 
       
            else{
                i++;
            }
        } 
        return s.size(); 
    } 
      
    public static void main(String[] args){ 
        Vector<String> s = new Vector<>(); 
  
        s.addElement("ab"); 
        s.addElement("aa"); 
        s.addElement("aa");
        s.addElement("bcd");
        s.addElement("ab");
  
        System.out.println(removeConsSame(s)); 
    } 
}
3

複雜度分析

時間複雜度

O(n ^ 2) 其中n是列表中的字符串數。 由於我們正在從向量中刪除字符串。 從向量中刪除任何元素都需要線性時間。 因為此操作可以執行N次。 時間複雜度是多項式。

空間複雜度

O(1) 因為我們沒有使用任何中間數據結構來存儲信息。 存儲字符串所需的唯一空間是輸入的一部分,在計算算法的空間複雜度時不會考慮。 但是整個程序仍然需要O(N)空間。