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 .
Contact Us