המרת זיגזג


רמת קושי בינוני
נשאל לעתים קרובות פייפאל
מחרוזת

בבעיית המרת זיגזג נתנו א מחרוזת s באורך n ומספר שלם r המייצג את מספר השורות. המר את המחרוזת הנתונה בתבנית הזגזג של שורות r ושרשר את התווים בשורה. הדפס את המחרוזת המשורשרת החדשה.

המרת זיגזג

דוגמה

קלט: 

s = “TutorialCup”

R = 3

פלט: TrCuoilutap

קלט: 

s = "תכנות"

R = 4

פלט: Pmramoriggn

הסבר להמרה בזיגזג

תנו למחרוזת s = "TutorialCup" ולמספר השורות כלומר r = 3

אתחל מערך מחרוזות a] בגודל r ליצירת דפוס הזיגזג. בנוסף, אתחל שורה משתנה שלמה כדי לעקוב אחר השורה הנוכחית כ- 0 ומשתנה בוליאני למטה.

התחל לחצות את המחרוזת ועדכן את מערך המיתרים באופן הבא. להלן השלבים לדוגמא לעיל -

  • 1: שורה = 0, למטה = נכון, [] = T
  • 2: שורה = 1, למטה = אמת, a [] = T, u
  • 3: שורה = 2, למטה = שקר, a [] = T, u, t
  • 4: שורה = 1, למטה = נכון, a [] = T, uo, t
  • 5: שורה = 0, למטה = נכון, a [] = Tr, uo, t
  • 6: שורה = 1, למטה = נכון, a [] = Tr, uoi, t
  • 7: שורה = 2, למטה = שקר, a [] = Tr, uoi, ta
  • 8: שורה = 1, למטה = נכון, a [] = Tr, שמן, טא
  • 9: שורה = 0, למטה = נכון, a [] = TrC, נפט, טא
  • 10: שורה = 1, למטה = אמת, a [] = TrC, uoilu, ta
  • 11: שורה = 2, למטה = שקר, a [] = TrC, uoilu, הקש

לכן, המחרוזת המתקבלת היא TrCuoilutap

אלגוריתם להמרה בזיגזג

  1. אתחל מחרוזת s באורך n ומספר שלם r המייצג את מספר השורות.
  2. אם מספר השורות (r) הנתון הוא מחרוזת החזרה אחת.
  3. צור מערך בגודל r מסוג מחרוזות.
  4. אתחל את השורה כ- 0 ומטה מהסוג הבוליאני.
  5. חצה בין 0 ל- n-1 ואחסן את הדמויות של מחרוזת במערך מחרוזות בשורת אינדקס.
  6. בדוק אם השורה שווה לעדכון r-1 למטה כשקר.
  7. אחרת אם השורה היא 0 עדכונים למטה כנכונה.
  8. אם למטה נכון התוספת השורה אחרת מקטינה את השורה.
  9. הדפיסו את מערך המיתרים המעודכן.

תכנית C ++ להמרת זיגזג

#include<bits/stdc++.h> 
using namespace std; 
  
void ZigZag(string s, int r){ 
    
    if(r == 1){ 
        cout<<s;       
        return; 
    }    
  
    int n = s.length(); 
  
    string a[r]; 
  
    int row = 0; 
    bool down; 
    
    for(int i=0; i<n; ++i){ 
        
        a[row].push_back(s[i]); 
  
        if(row == r-1) 
          down = false; 
  
        else if (row == 0) 
          down = true; 
  
        (down)? (row++): (row--); 
    } 
  
    for(int i=0; i<r; ++i) 
        cout<<a[i]; 
} 

int main(){ 
    string s = "TutorialCup"; 
    int r = 3; 
    ZigZag(s, r); 
    return 0; 
}
TrCuoilutap

תוכנית Java להמרת זיגזג

import java.util.Arrays; 
  
class Concatenate{ 
  
    static void ZigZag(String s, int r){ 
  
        if(r == 1){ 
            System.out.print(s); 
            return; 
        } 
        
        char[] str = s.toCharArray(); 
  
        int n = s.length(); 
  
        String[] a = new String[r]; 
        Arrays.fill(a, ""); 
  
        int row = 0; 
        boolean down = true;
        
        for(int i=0; i<n; ++i){ 
            
            a[row] += (str[i]); 
  
            if(row == r-1){ 
                down = false; 
            }  
              
            else if(row == 0){ 
                down = true; 
            } 
  
            if(down){ 
                row++; 
            }  
            else{ 
                row--; 
            } 
        } 
  
        for(int i=0; i<r; ++i){ 
            System.out.print(a[i]); 
        } 
    } 
  
    public static void main(String[] args){
        
        String s = "TutorialCup"; 
        int r = 3; 
        ZigZag(s, r);
        
    } 
}
TrCuoilutap

ניתוח מורכבות להמרת זיגזג

מורכבות זמן: O (n) כאשר n הוא גודל מחרוזת הקלט.

מרחב עזר: O (n) מכיוון שאנו שומרים את התשובה במערך (של סוג מחרוזת) בזמן חישוב התשובה.

הפניות