Бацкспаце Стринг Цомпаре  


Ниво тешкоће Лако
Често питани у амазонка ЦодеНатион фацебоок гоогле мицрософт пророчанство
Стацк низ Тво Поинтер Тво Поинтерс

У задатку упоређивања повратног низа дали смо два Жице С и Т, проверите да ли су једнаки или не. Имајте на уму да низови садрже '#' што значи повратни знак.

Примери  

Улазни
С = "аб # ц"
Т = „оглас # ц“
Излаз
тачно (пошто се и С и Т претварају у „ац“)

Улазни
С = "аб ##"
Т = „ц # д #“
Излаз
тачно (пошто су и С и Т празни)

Улазни
С = „а # ц“
Т = "б"
Излаз
нетачно (као С = "ц" и Т = "б")

Наивни приступ за поређење бацкспаце низа  

Ово је основни приступ који заузима мало додатног простора за решавање проблема упоређивања повратних низова. Дођимо до логике како то решити.

Пређите низом С и Т и реформишите обе жице, односно уклоните знакове на које ће бацкспаце утицати.
Пример
С = "аб # ц" се преобликује у С = "ац", јер се б уклања због повратног простора

Бацкспаце Стринг ЦомпареПин

Затим упоредите два нова низа, ако су једнаки ретурн труе иначе ретурн фалсе.

Реформација низа се врши као,

  1. Створите празан низ знакова.
  2. Започните кретање низом од индекса 0.
  3. Ако је тренутни знак '#' и стек није празно, искочите ставку из гомиле.
  4. Иначе, ако тренутни знак није '#', гурните тренутни знак у стек.
  5. Након потпуног преласка низа, стек садржи реформисани низ у обрнутом редоследу.
Види такође
Број НГЕ-а удесно

Анализа сложености за упоређивање бацкспаце низа

Сложеност времена = О (н + м), где је н дужина низа С, а м дужина низа Т.
Сложеност простора = О (н + м)

ЈАВА код

import java.util.Stack;

public class BackspaceStringCompare {
    private static boolean backSpaceCompare(String S, String T) {
        // Reform the strings and check if they are equal
        return reform(S).equals(reform(T));
    }

    // Function to reform a string
    private static String reform(String S) {
        char sArr[] = S.toCharArray();
        // Create an empty stack
        Stack<Character> stack = new Stack<>();

        // Traverse in the string
        for (int i = 0; i < sArr.length; i++) {
            // If current character is # and stack is empty, pop out an item from stack
            if (sArr[i] == '#' && !stack.isEmpty()) {
                stack.pop();
            }
            // If current character is not #, push it into the stack
            if (sArr[i] != '#') {
                stack.push(sArr[i]);
            }
        }

        // Stack contains the string in reverse order, return the reversed string
        // As it does not affect the comparision
        return String.valueOf(stack);
    }

    public static void main(String[] args) {
        // Example 1
        System.out.println(backSpaceCompare("ab#c", "ad#c"));

        // Example 2
        System.out.println(backSpaceCompare("ab##", "c#d#"));

        // Example 3
        System.out.println(backSpaceCompare("a#c", "b"));
    }
}

Ц ++ код

#include <bits/stdc++.h>
using namespace std;

// Function to reform a string
string reform(char *s, int n) {
    // Create an empty stack
    stack<char> st;
    
    // Traverse in the string
    for (int i = 0; i < n; i++) {
        // If current character is # and stack is empty, pop out an item from stack
        if (s[i] == '#' && !st.empty()) {
            st.pop();
        }
        // If current character is not #, push it into the stack
        if (s[i] != '#') {
            st.push(s[i]);
        }
    }
    
    // Stack contains the string in reverse order, return the reversed string
    // As it does not affect the comparision
    char str[st.size()];
    for (int i = 0; i < st.size(); i++) {
        str[i] = st.top();
        st.pop();
    }
    
    string ans = str;
    return ans;
}

bool backSpaceCompare(char *s, char *t, int n, int m) {
    // Reform the strings and check if they are equal
    if (reform(s, n).compare(reform(t, m)) == 0) {
        return true;
    }
    return false;
}

int main() {
    // Example 1
    if (backSpaceCompare("ab#c", "ad#c", 4, 4)) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }

    // Example 2
    if (backSpaceCompare("ab##", "c#d#", 4, 4)) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }

    // Example 3
    if (backSpaceCompare("a#c", "b", 3, 1)) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }
    
    return 0;
}
S = "ab#c"
T = "ad#c"
true

Оптимални приступ за поређење бацкспаце низа  

Временска сложеност наивног приступа не може се даље смањивати, али сложеност простора може се оптимизовати на О (1).

Види такође
Образложење текста

Пређите низом С и Т обрнутим редоследом, ако у било ком низу видимо знак за повратак ('#'), следећи не-бацкспаце знак тог низа се прескаче и упоређујемо само оне који нису прескочени.

  1. Иницијализујте две целобројне вредности сСкип и тСкип, у којима се чува број бацкспацеа на које се наилази.
  2. Ако видимо '#' у С, повећајте сСкип, а ако видимо '#' у Т повећавајте тСкип.
  3. Ако су сСкип и тСкип 0, упоредите тренутни карактер низова С и Т, ако су једнаки, наставите за преостали низ иначе враћа фалсе.
  4. Иначе ако сСкип није нула, прескочите тренутни знак у С и смањите сСкип за 1, слично ако тСкип није нула, прескочите тренутни знак у Т и смањите тСкип за 1.
  5. Понављајте горње кораке док не пређемо у потпуности једну од жица.
  6. За преостале знакове низа С, ако је тренутни знак '#', повећајте сСкип за 1, иначе га смањите за 1. Ако у било ком тренутку сСкип постане негативан, враћа фалсе.
  7. За преостале знакове низа Т, ако је тренутни знак '#', повећајте тСкип за 1, иначе га смањите за 1. Ако у било ком тренутку тСкип постане негативан, враћа се фалсе.
  8. Ако су горе наведени услови сигурно испуњени (то је без враћања нетачног), вратите тачно.

Анализа сложености за упоређивање бацкспаце низа

Сложеност времена = О (м + н), где је н дужина низа С, а м дужина низа Т.
Сложеност простора = О (1)

ЈАВА код

public class BackspaceStringCompare {
    private static boolean backSpaceCompare(String S, String T) {
        char sArr[] = S.toCharArray();
        char tArr[] = T.toCharArray();

        int sP = sArr.length - 1;
        int tP = tArr.length - 1;
        // Initialize sSkip and tSkip as 0
        int sSkip = 0;
        int tSkip = 0;

        // Traverse the strings in reverse order
        while (sP >= 0 && tP >= 0) {
            // If current character in S is '#', increment sSkip
            if (sArr[sP] == '#') {
                sSkip++;
                sP--;
            }

            // If current character in T is '#', increment tSkip
            if (tArr[tP] == '#') {
                tSkip++;
                tP--;
            }

            // If the traversal for any one string is complete break the loop
            if (sP < 0 || tP < 0) {
                break;
            }

            // If both sSkip and tSkip are zero compare the current characters
            if (sSkip == 0 && tSkip == 0) {
                if (sArr[sP] == tArr[tP]) {
                    // Continue if these are equal
                    sP--;
                    tP--;
                } else {
                    // Else return false immediately
                    return false;
                }
            } else {
                // If current character in S is '#', increment sSkip
                if (sArr[sP] == '#') {
                    sSkip++;
                    sP--;
                } else {
                    // If sSkip is not 0, skip the current character
                    if (sSkip != 0) {
                        sSkip--;
                        sP--;
                    }
                }

                // If current character in T is '#', increment tSkip
                if (tArr[tP] == '#') {
                    tSkip++;
                    tP--;
                } else {
                    // If tSkip is not 0, skip the current character
                    if (tSkip != 0) {
                        tSkip--;
                        tP--;
                    }
                }
            }
        }

        // Traverse the remaining S string
        while (sP >= 0) {
            // If current character is '#', increment sSkip
            if (sArr[sP] == '#') {
                sSkip++;
            } else {
                // Else decrement sSkip
                sSkip--;
            }

            // If sSkip becomes negative return false
            if (sSkip < 0)
                return false;

            sP--;
        }

        // Traverse the remaining T string
        while (tP >= 0) {
            // If current character is '#', increment tSkip
            if (tArr[tP] == '#') {
                tSkip++;
            } else {
                // Else decrement tSkip
                tSkip--;
            }

            // If tSkip becomes negative, return false
            if (tSkip < 0) {
                return false;
            }

            tP--;
        }

        // Return true if encountered above cases safely
        return true;
    }

    public static void main(String[] args) {
        // Example 1
        System.out.println(backSpaceCompare("ab#c", "ad#c"));

        // Example 2
        System.out.println(backSpaceCompare("ab##", "c#d#"));

        // Example 3
        System.out.println(backSpaceCompare("a#c", "b"));
    }
}

Ц ++ код

#include <bits/stdc++.h>
using namespace std;

bool backSpaceCompare(char *S, char *T, int n, int m) {
    int sP = n - 1;
    int tP = m - 1;
    
    // Initialize sSkip and tSkip as 0
    int sSkip = 0;
    int tSkip = 0;
    
    // Traverse the strings in reverse order
    while (sP >= 0 && tP >= 0) {
        // If current character in S is '#', increment sSkip
        if (S[sP] == '#') {
            sSkip++;
            sP--;
        }
        
        // If current character in T is '#', increment tSkip
        if (T[tP] == '#') {
            tSkip++;
            tP--;
        }
        
        // If the traversal for any one string is complete break the loop
        if (sP < 0 || tP < 0) {
            break;
        }
        
        // If both sSkip and tSkip are zero compare the current characters
        if (sSkip == 0 && tSkip == 0) {
            if (S[sP] == T[tP]) {
                // Continue if these are equal
                sP--;
                tP--;
            } else {
                // Else return false immediately
                return false;
            }
        } else {
            // If current character in S is '#', increment sSkip
            if (S[sP] == '#') {
                sSkip++;
                sP--;
            } else {
                // If sSkip is not 0, skip the current character
                if (sSkip != 0) {
                    sSkip--;
                    sP--;
                }
            }
            
            // If current character in T is '#', increment tSkip
            if (T[tP] == '#') {
                tSkip++;
                tP--;
            } else {
                // If tSkip is not 0, skip the current character
                if (tSkip != 0) {
                    tSkip--;
                    tP--;
                }
            }
        }
    }
    
    // Traverse the remaining S string
    while (sP >= 0) {
        // If current character is '#', increment sSkip
        if (S[sP] == '#') {
            sSkip++;
        } else {
            // Else decrement sSkip
            sSkip--;
        }
        
        // If sSkip becomes negative return false
        if (sSkip < 0)
            return false;
        sP--;
    }
    
    // Traverse the remaining T string
    while (tP >= 0) {
        // If current character is '#', increment tSkip
        if (T[tP] == '#') {
            tSkip++;
        } else {
            // Else decrement tSkip
            tSkip--;
        }
        
        // If tSkip becomes negative, return false
        if (tSkip < 0) 
            return false;
        tP--;
    }
    
    // Return true if encountered above cases safely
    return true;
}

int main() {
    // Example 1
    if (backSpaceCompare("ab#c", "ad#c", 4, 4)) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }

    // Example 2
    if (backSpaceCompare("ab##", "c#d#", 4, 4)) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }

    // Example 3
    if (backSpaceCompare("a#c", "b", 3, 1)) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }
    
    return 0;
}
S = "ab##"
T = "c#d#"
true

Референце