Intuition Explained || Simple Simulation || C++ Clean Code
Approach 1: \nIntuition :\n\n Idea here is to just do what we are asked to perform. That is simulate decoding steps. \n First, we need to make cipher matrix usi
# **Approach 1:** \n**Intuition :**\n\n* Idea here is to just do what we are asked to perform. That is **simulate** decoding steps. \n* First, we need to make `cipher` matrix using `encodedText`. \n* Then, for each column in first row, we traverse diagonally and add those characters to `decodedText` string.\n* In the end, since trailing spaces are not allowed, so we remove it from `decodedString`. \n* We can have two cases. \n\t* One when `rows = 1`. In this case, we `decodedText` is same as `encodedText`.\n\t* And other when `rows > 1`. In this, we need to perform above simulation. \n\n* Lets understand through simple example : \n\n\t\tCase 1 : if rows == 1\n\t\t\t\t\t\t\n\t\t  Ex: "c o d i n g"\n            \n\t\t\t-> In this case we do not need to decode text. We can simply return encodedText directly. \n\t\t\t-> This is because all characters are in first row.\n\t\t\n\t\tCase 2: if rows > 1\n\t\t\t\t\t\t\n\t\t\tEx: encodedText = "ch   ie   pr" , rows = 3\n\t\t\t\n\t\t\tcipher matrix : \n\t\t\t\t  "c h _ _\n\t\t\t       _ i e _  \n\t\t\t\t   _ _ p r"\n           \n\t\t   -> Note : Here, just for sake of explanation, I have take space(" ") as underscore(_).\n\t\t   \n            i. k = 0 => {(0,0) : \'c\'}, {(1,1) : \'i\'}, {(2,2) : \'p\'} \n            ii. k = 1 => {(0,1) : \'h\'}, {(1,2) : \'e\'}, {(2,3) : \'r\'}\n\t\t\tiii. k = 2 => {(0,2) : \'_\'}, {(1,3) : \'_\'}\n\t\t\t\n\t\t\tThus, decodedString with trailing spaces = "cipher_ _". \n\t\t\tWe need to remove these trailing spaces, and then return resultant string.\n        \n\t\t\t\n# Code :\n\n```\nclass Solution {\npublic:\n    string decodeCiphertext(string encodedText, int rows) {\n        \n        if(rows == 1) {\n            return encodedText;\n        }\n        \n        int cols = encodedText.size() / rows;\n        \n        vector<vector<char>> cipher(rows, vector<char>(cols));\n        \n        int k = 0;\n        for(int i=0; i<rows; i++) {\n            for(int j=0; j<cols; j++) {\n                cipher[i][j] = encodedText[k++];\n            }\n        }\n        \n\t\t// Just added to print cipher \n        // for(auto& r : cipher) {\n        //     for(auto& c : r) {\n        //         cout << c << " ";\n        //     }\n        //     cout << endl;\n        // }\n        \n        string decodedText = "";\n\t\t\n\t\t// Traverse diagonally for each column\n        for(int k=0; k<cols; k++) {\n            int i=0, j=k;\n            while(i<rows && j<cols) {\n                decodedText.push_back(cipher[i++][j++]);\n            }\n        }\n        \n        // Remove trailing spaces\n        while(decodedText.back() == \' \') {\n            decodedText.pop_back();\n        }\n        \n        return decodedText;\n    }\n};\n```\n\n**Complexity :**\n\n* Time : `O(N + N)`, create `cipher` matrix, and build `decodedText` string.\n\t* N is size of `encodedText` string\n\n* Space : `O(N)`, for `cipher` matrix for simulation.\n-------------------------------------------------------\n------------------------------------------------------\n# **Approach 2:** \n\n**Intuition :**\n\n* We can optimize it further, by skipping `cipher` matrix part. We can directly get using `encodedText.` \n\n* Idea here is to move `(col+1)` steps each time in `encodedText`, to get next diagonal element. \n* Since, if we are some coordinate `[i,j]`, then next diagonal element i.e `[i+1, j+1]`. \n* Now, this is at a distance `(cols + 1)` from `[i,j]`. \n* So we can directly move by this distance to get next character of `decodedText`\n\n# Code : \n\n```\nstring decodeCiphertext(string encodedText, int rows) {\n        \n\tint n = encodedText.size();\n\tint cols = n / rows;\n\n\tstring decodedText = "";\n\n\tfor(int i=0; i < cols; i++) {\n\t\t// Move by distance (col+1) to get next character\n\t\tfor(int j=i; j<n; j += (cols+1)) {\n\t\t\tdecodedText += encodedText[j];\n\t\t}\n\t}\n\n\twhile(decodedText.back() == \' \') decodedText.pop_back();\n\n\treturn decodedText;\n}\n```\n\n***If you find this helpful, do give it a like :)***
['String', 'C', 'Simulation']