Reverse a c-style string
Posted on January 18, 2014
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
For example if a user enters a string “kodeknight” then on reversing the string will be “thginkedok“.
The basic approach here is to swap the first half of the string, with the next half.
Method 1 - Iterative using string length
#include<stdio.h> int string\_length(char\*); void reverse(char\*); int main() { char string\[100\]; printf("Enter a string\\n"); gets(string); reverse(string); printf("Reverse of entered string is \\"%s\\".\\n", string); return 0; } void reverse(char \*string) { int length, i; char \*begin, \*end, temp; length = string\_length(string); begin = string; end = string; for ( i = 0 ; i < ( length - 1 ) ; i++ ) end++; // swap the chars till half of the length of the string //begin with the end char and so on for ( i = 0 ; i < length/2 ; i++ ) { temp = \*end; \*end = \*begin; \*begin = temp; begin++; end--; } } int string\_length(char \*ptr) { int len = 0; while( \*(ptr+len) !
[Read More]Eliminate the pairs (two same chars adjacent to each other) in string
Posted on January 18, 2014
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
Problem:
You are given a string. You have to eliminate the pairs (two same chars adjacent to each other).
eg. input string RGBBGBGR –> RGGBGR–> RBGR (output)
Solution:
We should check if we have character pair then cancel it. and then check for next character and previous character. Keep canceling the character until we either reach start of the array or end of the array or not find a pair.
[Read More]Move the Spaces to Front of the String
Posted on January 18, 2014
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
Problem: Given a string that has set of words and spaces, write a program to move the spaces to front of string, you need to traverse the array only once and need to adjust the string in place.
string = “move these spaces to beginning”
output =” movethesepacestobeginning”
Solution:
Maintain two indices i and j. Traverse from end to beginning.
If the current index contains char, swap chars in index i with index j.
[Read More]Replace all spaces in a string with “%20″ in c-style string
Posted on January 18, 2014
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
Problem Write a C program that will replace all spaces with ‘%20′
Example
Input: “Mr John Smith "
Output: “Mr%20John%20Smith
Solution The algorithm is as follows:
Count the number of spaces during the first scan of the string. Parse the string again from the end and for each character:
If a space is encountered, store “%20”.
Else, store the character as it is in the newly shifted location.
[Read More]Given a dictionary of word - Group all words into set of anagrams of each other
Posted on August 10, 2013
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
Given a set of words in a dictionary, write a program to group all words which are anagrams of each other in to sets.
input: “bat”, “tar”, “xyz” , “tab”, “tar” output:[[“bat”, tab”], [“tar”, rat”],”xyz” ]
Anagrams
Two words are anagrams if one of them has exactly same characters as that of the another word.
Example : Anagram & Nagaram are anagrams (case-insensitive).
Approach
The simpler logic would be to :
[Read More]Boyer Moore Algorithm
Posted on August 9, 2013
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
String Searching Algorithm - Knuth Morris Pratt or KMP Algorithm
Posted on July 30, 2013
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
Knuth-Morris-Pratt string searching algorithm:
- This algorithm searches a word->w within the main string text->s
- Such a search must employ the following observation:
i) A given match determines where the next match could begin
ii) The above intelligence is obtained for the search word itself that contains sufficient information for making such a discussion (i.e. determine where the next match begins)
Advantage of this string searching algorithm: Helps to avoid the re-examination of already matched characters
[Read More]Check if 2 strings are rotated versions of each other
Posted on December 31, 2011
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
Problem : Given two string s1 and s2 how will you check if s1 is a rotated version of s2 ?
OR
Assume you have a method isSubstring() which checks if one word is a substring of another. Given two strings, s1 and s2, write code to check if s2 is a rotation of s1 using only one call to isSubstring.ie: ‘waterbottle’ is a rotation of ‘erbottlewat’
[Read More]Escape all % characters in a string; % is the escape character
Posted on December 31, 2011
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
Example :
Input : India has GDP of 10% in 2009
Output : Input has GDP of 10%% in 2009
It is usually not be possible to do this in-place since the original unescaped string may not have enough space in the array to store the additional escape characters. But if we create a new array, O(n) algo is possible, though space complexity will increase.
String escapePercent(String input) { StringBuilder sb = new StringBuilder(); char\[\] str = input.
[Read More]Remove whitespace from a string in-place, in linear time
Posted on December 31, 2011
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
Should not there be a \o in the end to terminate t… Neha - Oct 2, 2013Should not there be a \o in the end to terminate the string??
Yes this is a ‘\0’ terminated string only. We are moving ahead only when we find a white space (when we say):
while (str[ahead] == ' ‘) ahead++;
Rest all the characters except the space are copied as is, which also includes ‘\0’ and hence string is ‘\0’ .
[Read More]