Loading presentation...

Present Remotely

Send the link below via email or IM


Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.



No description

Kalyan Sonnathi

on 22 March 2013

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Strings

Basics Problem Patterns Problems Strings What is a string? Are these always strings? A int *
A int []
A char *
A char [] In C, it is a null terminated sequence of chars Allocating strings Stack allocation
char arr1[10]
Heap allocation
char *arr2 = (char*)malloc(10)
char * arr = "HelloWorld"
Null char takes space too !
Mutability Write code to modify with 10 a's and discuss your observations
a char []
a char * on heap
a literal sizeof vs strlen For each of the following, print out sizeof and strlen char arr1[10] = {"hello"}
char * arr2 = ....
char * arr3 = "hello" Common Problems Stack Corruption
Heap Corruption
Very hard to debug :)
Exercise: Corrupt the stack and heap Moral of the story Be careful with string arithmetic and size calculations.
Do you own the bytes you are writing to?
Remember that \0 takes space too.
Common Form Scan the string in some order
Take some action during the scan
keep a count
Modify the string
Copy it to some other location etc.
Left to Right Scans Examples:

Right to left scans Examples
Shift string
Insert string
Two Pointers Moving in opposite directions

Reverse Per Character stats Sort
Remove duplicates
Two Pointers Moving in same direction

Remove spaces

For each of the problems

What pattern will you use?
Modify inplace or not?
What are the test cases?
Boundary (any cases where we can corrupt?)
Change case of every char Remove all digits in a string Repeat each character ("abc",2) -> aabbcc
("abc",3) -> aaabbbccc a1b2c -> abc AbCdE -> aBcDe Repeat whole string ("abc",2) -> abcabc Phone Mapping abcd -> 2223 Anagrams "pot", "top" -> true
"pot", "tip" -> false Run length Encoding aaaaabbcccdd -> a5b2c3d2
Full transcript