I have a problem where I want to find the longest common prefix of N strings given in an array.
Below is a perfectly working code:
def longestCommonPrefix(S) :
if (len(S) == 0):
return ""
for i in range(len(S[0])):
c = S[0][i]
for j in range(len(S)):
if (i == len(S[j]) or S[j][i] != c):
return S[0][0:i];
return S[0]
X = ["Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt anim id est laborum.",
"Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod td exercitation ullamcon reprehenderit int occaecat cupidatat nonmollit anim id est laborum.",
"Lorem ipsum dolor sit amet, consectetur adipiscing elit, ccaecat cupidatat nonmollit anim id est laborum.",
"Lorem ipsum dolor sit amet, consectetur adrit int occaecat cupidatat nonmollit anim id est laborum."]
print(longestCommonPrefix(X))
>> 'Lorem ipsum dolor sit amet, consectetur ad'
PROBLEM: When I have my text array as:
X = [
'Class- VII-CBSE-Mathematics\\nIntegers\ne EMBIBE\nThe temperature at Srinagar \\( =-2^{\\circ} \\mathrm{C} \\)\nTherefore, the difference \\( =-2^{\\circ} \\mathrm{C}-\\left(-8^{\\circ} \\mathrm{C}\\right) \\) \\( =6^{\\circ} \\mathrm{C} \\)\n(d) The temperature of Srinagar and Shimla taken together \\( =-2^{\\circ} \\mathrm{C} 5^{\\circ} \\mathrm{C} \\) \\( =3^{\\circ} \\mathrm{C} \\)\nThe temperature at Shimla \\( =5^{\\circ} \\mathrm{C}>3^{\\circ} \\mathrm{C} \\). Therefore the temperature of Srinagar and Shimla taken together is less than that of Shimla.\n\nThe temperature at Srinagar \\( =-2^{\\circ} \\mathrm{C}<3^{\\circ} \\mathrm{C} \\). Therefore, the temperature of Srinagar and Shimla taken together is not less than that of Srinagar',
'Class- VII-CBSE-Mathematics\\nIntegers\ne EMBIBE\nSubmarine floating below the sea level \\( =1200 \\mathrm{~m} \\)\nTherefore, the vertical distance between them \\( =5000 1200 \\)\n\\[\n=6200 \\mathrm{~m}\n\\]',
'Class- VII-CBSE-Mathematics\\nIntegers\ne EMBIBE\n\\begin{tabular}{|c|c|c|}\n\\hline\\( -4 \\) & \\( -3 \\) & \\( -2 \\) \\\\\n\\hline\\( -6 \\) & 4 & \\( -7 \\) \\\\\n\\hline\n\\end{tabular}', '\n(i) Sum of the rows:\n\\[\n\\begin{array}{l}\n5 -1 -4=0 \\\\\n-5 -2 7=0 \\\\\n0 3 -3=0\n\\end{array}\n\\]\nSum of the columns:\n\\[\n\\begin{array}{l}\n5 -5 0=0 \\\\\n-1 -2 3=0 \\\\\n-4 7 -3=0\n\\end{array}\n\\]\nSum of the diagonals:\n\\[\n\\begin{array}{l}\n5 -2 -3=0 \\\\\n-4 -2 0=-6\n\\end{array}\n\\]\nThus, this is not a magic square because all the sums are not equal\n(ii) Sum of the rows:\n\\[\n\\begin{array}{l}\n1 -10 0=-9 \\\\\n-4 -3 -2=-9 \\\\\n-6 4 -7=-9\n\\end{array}\n\\]\nSum of the columns:\n\\[\n\\begin{array}{l}\n1 -4 -6=-9 \\\\\n-10 -3 4=-9 \\\\\n0 -2 -7=-9\n\\end{array}\n\\]\nSum of the diagonals:\n\\[\n\\begin{array}{l}\n1 -3 -7=0 \\\\\n0 -3 -6=-9\n\\end{array}\n\\]\nThus, this is a magic square because all the sums are equal',
'Class- VII-CBSE-Mathematics\\nIntegers\ne EMBIBE\n(ii) \\( a=118, b=125 \\)\n(iii) \\( \\mathrm{a}=75, \\mathrm{~b}=84 \\)\n(iv) \\( a=28, b=11 \\)', '\n\\[\n\\begin{array}{l}\n\\text { LHS } a-(-b)=21-(-18)=39 \\\\\n\\text { RHS } a b=21 18=39 \\\\\n\\mathrm{LHS}=\\text { RHS }\n\\end{array}\n\\]\nThus verified\n\\[\n\\begin{array}{l}\n\\operatorname{LHS~} a-(-b)=118-(-125)=243 \\\\\n\\text { RHS a } b=118 125=243 \\\\\n\\mathrm{LHS}=\\text { RHS }\n\\end{array}\n\\]\nThus verified\n\\[\n\\begin{array}{l}\n\\operatorname{LHS~} a-(-b)=75-(-84)=159 \\\\\n\\text { RHS } a b=75 84=159 \\\\\n\\text { LHS }=\\text { RHS }\n\\end{array}\n\\]\nThus verified\n\\[\n\\begin{array}{l}\n\\operatorname{LHS~} a-(-b)=28-(-11)=39 \\\\\n\\text { RHS } a b=28 11=39\n\\end{array}\n\\]\n\\[\n\\mathrm{LHS}=\\mathrm{RHS}\n\\]\nThus verified',
'Class- VII-CBSE-Mathematics\\nIntegers\ne EMBIBE\n(c) \\( -7>-29 \\)\n(d) \\( 0<20 \\)\n(e) \\( -101>-159 \\)',
]
I get the result as '' EMPTY string. Can someone please help me with it.
given on the suggestion for the below answer, I also did:
def replace(x):
for i in ["\\","\n","\t",'\"',"\'","\b","\f","\r"]:
x = x.replace(i,"`")
return x
X = [replace(i) for i in X]
I have also tried doing X = [repr(i) for i in X]
But still I get the same "" answer.
CodePudding user response：
The data are malformed. I've made an assumption about what it should look like by escaping four single-quotes which results in the X list containing 5 elements (which is what I think is expected).
I then implemented the longest common prefix function like this:
X = [
'Class- VII-CBSE-Mathematics\\nIntegers\ne EMBIBE\nThe temperature at Srinagar \\( =-2^{\\circ} \\mathrm{C} \\)\nTherefore, the difference \\( =-2^{\\circ} \\mathrm{C}-\\left(-8^{\\circ} \\mathrm{C}\\right) \\) \\( =6^{\\circ} \\mathrm{C} \\)\n(d) The temperature of Srinagar and Shimla taken together \\( =-2^{\\circ} \\mathrm{C} 5^{\\circ} \\mathrm{C} \\) \\( =3^{\\circ} \\mathrm{C} \\)\nThe temperature at Shimla \\( =5^{\\circ} \\mathrm{C}>3^{\\circ} \\mathrm{C} \\). Therefore the temperature of Srinagar and Shimla taken together is less than that of Shimla.\n\nThe temperature at Srinagar \\( =-2^{\\circ} \\mathrm{C}<3^{\\circ} \\mathrm{C} \\). Therefore, the temperature of Srinagar and Shimla taken together is not less than that of Srinagar',
'Class- VII-CBSE-Mathematics\\nIntegers\ne EMBIBE\nSubmarine floating below the sea level \\( =1200 \\mathrm{~m} \\)\nTherefore, the vertical distance between them \\( =5000 1200 \\)\n\\[\n=6200 \\mathrm{~m}\n\\]',
'Class- VII-CBSE-Mathematics\\nIntegers\ne EMBIBE\n\\begin{tabular}{|c|c|c|}\n\\hline\\( -4 \\) & \\( -3 \\) & \\( -2 \\) \\\\\n\\hline\\( -6 \\) & 4 & \\( -7 \\) \\\\\n\\hline\n\\end{tabular}\', \'\n(i) Sum of the rows:\n\\[\n\\begin{array}{l}\n5 -1 -4=0 \\\\\n-5 -2 7=0 \\\\\n0 3 -3=0\n\\end{array}\n\\]\nSum of the columns:\n\\[\n\\begin{array}{l}\n5 -5 0=0 \\\\\n-1 -2 3=0 \\\\\n-4 7 -3=0\n\\end{array}\n\\]\nSum of the diagonals:\n\\[\n\\begin{array}{l}\n5 -2 -3=0 \\\\\n-4 -2 0=-6\n\\end{array}\n\\]\nThus, this is not a magic square because all the sums are not equal\n(ii) Sum of the rows:\n\\[\n\\begin{array}{l}\n1 -10 0=-9 \\\\\n-4 -3 -2=-9 \\\\\n-6 4 -7=-9\n\\end{array}\n\\]\nSum of the columns:\n\\[\n\\begin{array}{l}\n1 -4 -6=-9 \\\\\n-10 -3 4=-9 \\\\\n0 -2 -7=-9\n\\end{array}\n\\]\nSum of the diagonals:\n\\[\n\\begin{array}{l}\n1 -3 -7=0 \\\\\n0 -3 -6=-9\n\\end{array}\n\\]\nThus, this is a magic square because all the sums are equal',
'Class- VII-CBSE-Mathematics\\nIntegers\ne EMBIBE\n(ii) \\( a=118, b=125 \\)\n(iii) \\( \\mathrm{a}=75, \\mathrm{~b}=84 \\)\n(iv) \\( a=28, b=11 \\)\', \'\n\\[\n\\begin{array}{l}\n\\text { LHS } a-(-b)=21-(-18)=39 \\\\\n\\text { RHS } a b=21 18=39 \\\\\n\\mathrm{LHS}=\\text { RHS }\n\\end{array}\n\\]\nThus verified\n\\[\n\\begin{array}{l}\n\\operatorname{LHS~} a-(-b)=118-(-125)=243 \\\\\n\\text { RHS a } b=118 125=243 \\\\\n\\mathrm{LHS}=\\text { RHS }\n\\end{array}\n\\]\nThus verified\n\\[\n\\begin{array}{l}\n\\operatorname{LHS~} a-(-b)=75-(-84)=159 \\\\\n\\text { RHS } a b=75 84=159 \\\\\n\\text { LHS }=\\text { RHS }\n\\end{array}\n\\]\nThus verified\n\\[\n\\begin{array}{l}\n\\operatorname{LHS~} a-(-b)=28-(-11)=39 \\\\\n\\text { RHS } a b=28 11=39\n\\end{array}\n\\]\n\\[\n\\mathrm{LHS}=\\mathrm{RHS}\n\\]\nThus verified',
'Class- VII-CBSE-Mathematics\\nIntegers\ne EMBIBE\n(c) \\( -7>-29 \\)\n(d) \\( 0<20 \\)\n(e) \\( -101>-159 \\)'
]
def lcp(sa):
assert len(sa) > 1
k, *r = sa
for o in range(min(map(len, sa))):
for e in r:
if e[o] != k[o]:
return k[:o]
return k
print(lcp(X))
Output:
Class- VII-CBSE-Mathematics\nIntegers
e EMBIBE
CodePudding user response：
Your code has problem. You are checking character by character and in your string there are escape characters like \n, \t, \b etc which are handled differently by Python. You can try substituting those in the first place and then compare the strings?
Like X = [i.replace("\n","$$").replace("\t","--").replace("\b",'##') for i in X]
One problem would be that your \begin would not make sense anymore but you can change that again string.replace("##','\b') later.