String programs¶

From GeeksforGeeks Python Programming Examples

Follow links to the originals for more details on the problem and Python solutions.

Is string a palindrome?¶

A string is a palindrome if it matches its reversal.

def isPal(str):
    r = range(0, len(str))
    lst = [str[i] for i in r]
    tsl = [str[-(i+1)] for i in r]
    return lst == tsl

>>> isPal("malayalam")
True

q){x~reverse x} "malayalam"
1b

Sort characters ¶

>>> ''.join(sorted('bbccdefbbaa'))
'aabbbbccdef'

q)asc "bbccdefbbaa"
`s#"aabbbbccdef"

Reverse words in a string ¶

>>> s = "i like this program very much"

>>> words = s.split(' ')
>>> " ".join([words[-(i+1)] for i in range(0, len(words))])
'much very program this like i'

q)s: "i like this program very much"

q)" " sv reverse " " vs s
"much very program this like i"

Q keywords vs and sv split and join strings.

Remove `i`th character from string ¶

>>> s = 'GeeksforGeeks'

>>> "".join([s[i] for i in range(0, len(s)) if i!=2])
'GeksforGeeks'

In q, til count x returns all the indexes of list x.

q)s:"GeeksforGeeks"

q)s (til count s) except 2
"GeksforGeeks"

Is string a substring of another?¶

>>> s = "geeks for geeks"

>>> s.find('geek')!= -1
True
>>> s.find('goon')!= -1
False

In q, the like keyword provides basic pattern matching.

q)s:"geeks for geeks"

q)s like "*geek*"
1b
q)s like "*goon*"
0b

Even-length words in a string ¶

>>> s = "This is a python language"

>>> [wrd for wrd in s.split(" ") if 0 == len(wrd) % 2]
['This', 'is', 'python', 'language']

q)s: "This is a python language"

q){x where 0=(count each x)mod 2} " " vs s
"This"
"is"
"python"
"language"

" " vs splits the string into a list of words. In the lambda, count each x is a vector of their lengths.

String contains all the vowels?¶

>>> s = 'geeks for geeks'

>>> all(["aeiou"[i] in s.lower() for i in range(0,5)])
False

q)s: "geeksforgeeks"

q)all "aeiou" in lower s
0b

"aeiou" in returns a list of flags, which all aggregates.

Count matching characters in two strings ¶

>>> str1 = 'aabcddekll12@'
>>> str2 = 'bb22ll@55k'

>>> len(set(str1) & set(str2))
5

q)str1: "aabcddekll12@"
q)str2: "bb22ll@55k"

q)count distinct str1 inter str2
5

In Python set() discards duplicate characters from each string. The q inter keyword is list intersection, not set intersection; distinct discards any duplicates.

Remove duplicates from a string ¶

>>> "".join(set("geeksforgeeks"))
'krgefso'

Q is a vector language. It has a keyword for this.

q)distinct "geeksforgeeks"
"geksfor"

The q keyword preserves order. The Python solution can be adapted to do the same.

>>> from collections import OrderedDict
>>> "".join(OrderedDict.fromkeys("geeksforgeeks"))
'geksfor'

String contains special characters?¶

>>> sc = '[@_!#$%^&*()<>?/\\|}{~:]'
>>> any([c in sc for c in set("Geeks$for$Geeks")])
True
>>> any([c in sc for c in set("Geeks for Geeks")])
False

q)sc:"[@_!#$%^&*()<>?/\\|}{~:]"   / special characters
q)any sc in "Geeks$For$Geeks"
1b
q)any sc in "Geeks For Geeks"
0b

Random strings until a given string is generated ¶

import string 
import random 
import time 

possibleCharacters = string.ascii_lowercase + string.digits + \
                     string.ascii_uppercase + ' ., !?;:'

# string to be generated 
t = "geek"

attemptThis = ''.join(random.choice(possibleCharacters) 
                                for i in range(len(t))) 
attemptNext = '' 

completed = False
iteration = 0

while completed == False: 
    print(attemptThis) 

    attemptNext = '' 
    completed = True

    # Fix the index if matches with 
    # the strings to be generated 
    for i in range(len(t)): 
        if attemptThis[i] != t[i]: 
            completed = False
            attemptNext += random.choice(possibleCharacters) 
        else: 
            attemptNext += t[i] 

    iteration += 1
    attemptThis = attemptNext 
    time.sleep(0.1) 

print("Target matched after " +
    str(iteration) + " iterations")

q)show pc:.Q.a,.Q.A,"0123456789 ., !?;:"    / possible characters
"abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789 ., !?;:"

q)tryfor:{i:where x<>y; @[y; i; :; count[i]?pc]}
q)s: tryfor["geek";] scan "    "
q)count s                                   / number of iterations
174

The binary q function tryfor first finds where string x varies from y, then replaces those letters with random picks from pc. Projecting tryfor onto "geek" yields a unary function.

q)tryfor["geek";] " e k"
"veIk"

Keyword scan applies tryfor["geek";] successively until the result stops changing, i.e. it finds a match.

The initial state is a string of blanks. scan returns the result of every iteration.

q)10 -10#\:s  / first and last 10 results
"    " "Czks" "T3cC" "d,s " "8pyi" ";DDG" "DVmh" "8Xoc" "JI!q" "q.NC"
"geeZ" "geef" "geeo" "gee9" "gee3" "geen" "gee," "geeR" "geeu" "geeN"

Split and join a string ¶

>>> '-'.join("Geeks for Geeks".split(' '))
'Geeks-for-Geeks'

q)"-"sv " " vs "Geeks for Geeks"
"Geeks-for-Geeks"

String is a binary?¶

>>> all([c in "01" for c in '01010101010'])
True

q)all "01010101010" in "01"
1b

Uncommon words from two strings ¶

import collections
# words that occur once only in string s
def singles(s):
    c = collections.Counter(s.split(' '))
    return[e[0] for e in c.items() if e[1]==1]

def uncommonWords(s1, s2):
    sw1 = singles(s1)
    sw2 = singles(s2)
    return [w for w in sw1+sw2 if not w in set(sw1)&set(sw2)]

>>> s1 = 'Greek for geeks'
>>> s2 = 'Learning from the the geeks'
>>> uncommonWords(s1, s2)
['Greek', 'for', 'Learning', 'from']

singles:{
  c:count each group`$" "vs x;
  key[c] where value[c]=1 }

uncommonWords:{
  sx:singles x;
  sy:singles y;
  (sx,sy) except sx inter sy }

q)s1:"Greek for geeks"
q)s2:"Learning from the the geeks"
q)uncommonWords[s1;s2]
`Greek`for`Learning`from

Permute a string ¶

from itertools import permutations 
>>> [''.join(w) for w in permutations('ABC')]
['ABC', 'ACB', 'BAC', 'BCA', 'CAB', 'CBA']

p:{$[x=2;(0 1;1 0);raze(til x)(rotate')\:(x-1),'.z.s x-1]}
permutations:{x p count x}

q)permutations "ABC"
"CAB"
"CBA"
"ABC"
"BAC"
"BCA"
"ACB"

Function p defines permutations of order \(N\) recursively. (.z.s allows a lambda to refer to itself.) permutations uses them to index its argument.

Reading Room: It’s more fun to permute for a non-recursive algorithm

URLs from string ¶

import re 

def findUrls(string): 
    rx = 'http[s]?://(?:[a-zA-Z]|[0-9]|[$-_@.&+]|[!*\(\), ]|(?:%[0-9a-fA-F][0-9a-fA-F]))+'
    return re.findall(rx, string)

>>> s = 'My Profile: https://auth.geeksforgeeks.org/user/Chinmoy%20Lenka/articles in the portal of http://www.geeksforgeeks.org/'
>>> findUrls(s)
['https://auth.geeksforgeeks.org/user/Chinmoy%20Lenka/articles in the portal of http://www.geeksforgeeks.org/']

findUrls:{
  begins:{y~count[y]#x};                            / x begins with y?
  c:(x ss "http")_x;                                / candidate substrings
  c:c where any c begins\:/:("http://";"https://"); / continue as URLs?
  {(x?" ")#x}each c }                               / take each up to space

q)s: "My Profile: https://auth.geeksforgeeks.org/user/Chinmoy%20Lenka/articles in the portal of http://www.geeksforgeeks.org/"
q)findUrls s
"https://auth.geeksforgeeks.org/user/Chinmoy%20Lenka/articles"
"http://www.geeksforgeeks.org/"

The published Python solution relies on a non-trivial RegEx to match any URL. (It also fails.)

The q solution looks for substring "http" and tests candidates to see whether they begin URLs.

Combining the iterators Each Left and Each Right \:/: allows us to test each of the candidate substrings in c against both http:// and https://.

Rotate a string ¶

def rotate(s,n): return ''.join([s[(i+n)%len(s)] for i in range(0, len(s))])

>>> rotate("GeeksforGeeks",2)
'eksforGeeksGe'
>>> rotate("GeeksforGeeks",-2)
'ksGeeksforGee'

q)2 rotate "GeeksforGeeks"
"eksforGeeksGe"
q)-2 rotate "GeeksforGeeks"
"ksGeeksforGee"

Empty string by recursive deletion?¶

def checkEmpty(string, sub): 
    if len(string)== 0: 
        return False
    while (len(string) != 0): 
        index = string.find(sub) 
        if (index ==(-1)): 
            return False
        string = string[0:index] + string[index + len(sub):]            
    return True

>>> checkEmpty("GEEGEEKSSGEK", "GEEKS")
False
>>> checkEmpty("GEEGEEKSKS", "GEEKS")
True

q)0=count ssr[;"GEEKS";""] over "GEEGEEKSSGEK"
0b
q)0=count ssr[;"GEEKS";""] over "GEEGEEKSKS"
1b

Projected onto two arguments (as ssr[;"GEEKS";""]) ternary string-replacement keyword ssr is a unary function.

The over keyword applies a unary function successively until the result stops changing.

It remains only to count the characters in the result of the last iteration.

If over gives an unexpected result, the matter is usually clarified by replacing it with scan, which performs the same computation but returns the result of each iteration.

q)ssr[;"GEEKS";""] scan "GEEGEEKSSGEK"
"GEEGEEKSSGEK"
"GEESGEK"
q)ssr[;"GEEKS";""] scan "GEEGEEKSKS"
"GEEGEEKSKS"
"GEEKS"
""

Scrape and find ordered words ¶

>>> url = "http://wiki.puzzlers.org/pub/wordlists/unixdict.txt"
>>> words = requests.get(url).content.decode("utf-8").split()
>>> len(words)
25104
>>> lists = [list(w.lower() for w in words]
>>> ow = [words[i] for i in range(0, len(words)) if lists[i] == sorted(lists[i])]
>>> len(ow)
422

q)url: "http://wiki.puzzlers.org/pub/wordlists/unixdict.txt"
q)words:system"curl ",url
q)count words
25104
q)ow:words where{x~asc x}each lower words
q)count ow
422

A q string is just a list of characters and can be sorted as it is.

Find possible words ¶

>>> d = ["go", "bat", "me", "eat", "goal", "boy", "run"]
>>> tray = list("eobamgl")

>>> [w for w in d if all([c in tray for c in w])]
['go', 'me', 'goal']

q)d:string`go`bat`me`eat`goal`boy`run           / dictionary
q)tray: "eobamgl"

q)d where all each d in\:tray
"go"
"me"
"goal"

Dictionary examples