Decode the String of special characters
Given an input string S of special characters where “@” represents “01“, “#@” represents “111” and “##” represents “00“. Decode the input string of special characters and print the number formed by decoding it.
Examples:
Input: S = “@#@##”
Output: 60
Explaination: @ represents “01” followed by #@ which represents “111”, followed by ## which represents “00”, On combining all associated strings we get “01” + “111” + “00” = “0111100” and it is binary representation of 60.Input: S = “##@”
Output: 1
Explanation: ## represents “00”, followed by @ which represents “01”, On combining both strings we get “00” + “01” = “0001” which is binary representation of 1.Input: S = “#@@#@##”
Output: 95
Explanation: #@ represents “111”, followed by @ which represents “01”, followed by #@ again which represents “111”, and ## at last which represents “00”On combining all the strings we get “111” + “01” + “111” + “00” = “1110111100” which is binary representation of 956.
Approach: To solve the problem follow the below idea:
Iterate over the input array and check that current character follows which pattern and choose the matching pattern among the given three and add the respective binary code to the answer string and then use the answer string to extract number.
This can be implemented by following the below mentioned steps:
- Initialize an empty string ans=”” ,we will add the extracted binary string to this string .
- Iterate over the input array length and for every single iteration perform the below mentioned steps :
- Check if current character is ‘@’ or not .If yes then add “01” to the ans string .
- If no this means current character is ‘#’ then check for next character of string .
- If next character is ‘#’ then add “00” to the ans string otherwise add “111” to the ans string .We checked for two characters and for avoiding repetition increment the value of i by 1 .
- Pass ans string to convertNumber and then return the received number.
Below Code is Implementation of above approach in C++.
C++
// C++ code for the above approach: #include <bits/stdc++.h> using namespace std; // Function to convert binary string // to decimal number int convertNumb(string n) { string num = n; int value = 0; // Initializing base value to 1, i.e 2^0 int base = 1; int len = num.length(); for ( int i = len - 1; i >= 0; i--) { if (num[i] == '1' ) value += base; base = base * 2; } return value; } // Main function that decodes special string // and returns extracted number int decode(string s) { // Decoded string string ans = "" ; int n = s.size(); // Iterating over the input string for ( int i = 0; i < n; i++) { // if current character is '@' then // add "01" to ans string because no // other pattern starts with '@' if (s[i] == '@' ) { ans += "01" ; } else { // if current character is '#' then // we need to check which pattern is // it so we need to check next character. if (s[i + 1] == '#' ) { // if next character is '#' then // the pattern is "##" so we add // "00" to ans string . ans += "00" ; } // The pattern is "#@" so we add // "111" to the ans string . else { ans += "111" ; } // Incrementing i by one because we // checked two characters and we // need to avoid repetition i++; } } // Passing the binary string to find the // number and returning it return convertNumb(ans); } // Drivers code int main() { string s = "#@@#@##" ; // Function call cout << decode(s); return 0; } |
Java
// Java code for the above approach: public class GFG { // Function to convert a binary string to a decimal // number public static int convertNumb(String n) { String num = n; int value = 0 ; // Initializing base value to 1, i.e., 2^0 int base = 1 ; int len = num.length(); for ( int i = len - 1 ; i >= 0 ; i--) { if (num.charAt(i) == '1' ) { value += base; } base = base * 2 ; } return value; } // Main function that decodes a special string and // returns the extracted number public static int decode(String s) { // Decoded string StringBuilder ans = new StringBuilder(); int n = s.length(); // Iterating over the input string for ( int i = 0 ; i < n; i++) { // If the current character is '@', then add // "01" to ans string because no other pattern // starts with '@' if (s.charAt(i) == '@' ) { ans.append( "01" ); } else { // If the current character is '#', we need // to check which pattern it is, so we need // to check the next character. if (i + 1 < n && s.charAt(i + 1 ) == '#' ) { // If the next character is '#', then // the pattern is "##", so we add "00" // to ans string. ans.append( "00" ); } else { // The pattern is "#@", so we add "111" // to the ans string. ans.append( "111" ); } // Incrementing i by one because we checked // two characters and we need to avoid // repetition i++; } } // Passing the binary string to find the number and // returning it return convertNumb(ans.toString()); } // Driver code public static void main(String[] args) { String s = "#@@#@##" ; // Function call System.out.println(decode(s)); } } |
Python3
# Python3 code for the above problem # Function to convert a binary string to a decimal number def convertNumb(binary_string): str_len = len (binary_string) value = 0 # Loop through all binary digits for i in range (str_len): # Check if the current bit is 1 and # Multiply it by the corresponding power of 2 if binary_string[str_len - 1 - i] = = "1" : value + = 2 * * i # Return the converted decimal value return value # Function that decodes special string def decode(special_str): n = len (special_str) ans = "" # variable to store converted string i = 0 # Counter to iterate through the input string while i < n: # If the current character is "@", add "01" to string if (special_str[i] = = "@" ): ans + = "01" # current character is "#" else : # check the next character if (special_str[i + 1 ] = = "#" ): ans + = "00" else : ans + = "111" # Increment i by 1 because we checked two characters i + = 1 # Increment i by 1 to move to the next character i + = 1 # Call convertNumb to convert the binary string to number return convertNumb(ans) # Driver code def main(): special_code = "#@@#@##" # Decode and print the results print (decode(special_code)) # Function call to execute the program main() # This code is contributed by Omkar Nitin Chorge (omkarchorge10) |
C#
// C# code for the above approach using System; public class GFG { // Function to convert binary string // to decimal number public static int ConvertNumb( string n) { string num = n; int value = 0; // Initializing base value to 1, i.e 2^0 int baseValue = 1; int len = num.Length; for ( int i = len - 1; i >= 0; i--) { if (num[i] == '1' ) value += baseValue; baseValue = baseValue * 2; } return value; } // Main function that decodes special string // and returns extracted number public static int Decode( string s) { // Decoded string string ans = "" ; int n = s.Length; // Iterating over the input string for ( int i = 0; i < n; i++) { // if current character is '@' then // add "01" to ans string because no // other pattern starts with '@' if (s[i] == '@' ) { ans += "01" ; } else { // if current character is '#' then // we need to check which pattern is // it so we need to check next character. if (s[i + 1] == '#' ) { // if next character is '#' then // the pattern is "##" so we add // "00" to ans string . ans += "00" ; } // The pattern is "#@" so we add // "111" to the ans string . else { ans += "111" ; } // Incrementing i by one because we // checked two characters and we // need to avoid repetition i++; } } // Passing the binary string to find the // number and returning it return ConvertNumb(ans); } // Drivers code public static void Main() { string s = "#@@#@##" ; // Function call Console.WriteLine(Decode(s)); } } // This code is contributed by Susobhan Akhuli |
Javascript
// JavaScript code of above approach // Function to convert binary // string to decimal number function convertNumb(n) { let num = n; let value = 0; // Initializing base value to 1, i.e. 2^0 let base = 1; let len = num.length; for (let i = len - 1; i >= 0; i--) { if (num[i] === '1' ) { value += base; } base *= 2; } return value; } // Main function that decodes special // string and returns extracted number function decode(s) { let ans = "" ; let n = s.length; // Iterating over the input string for (let i = 0; i < n; i++) { // if current character is '@' then // add "01" to ans string if (s[i] === '@' ) { ans += "01" ; } else { // if current character is '#' // then check next character if (s[i + 1] === '#' ) { // if next character is '#' then // the pattern is "##", add "00" // to ans string ans += "00" ; } else { // The pattern is "#@", add "111" // to the ans string ans += "111" ; } // Incrementing i by one because we // checked two characters and we need // to avoid repetition i++; } } // Passing the binary string to find // the number and returning it return convertNumb(ans); } // Driver code let s = "#@@#@##" ; // Function call console.log(decode(s)); |
956
Time Complexity: O(N), where N is the size of input string .
Auxiliary Space: O(M), where M is the generated binary string .