If the both do the same thing then which give us better accuracy?
There is a key difference:
Softmax regression provides class probabilities for mutually exclusive classes.
Logistic regression treats class membership for each class separately. Classes do not need to be mutually exclusive.
The two are equivalent for a scenario with two mutually exclusive classes - e.g. a "positive" and "negative" class - where softmax would have two outputs summing to 1, and logistic regression would have one output giving probability of the "positive" class.
I am not certain of the results comparing logistic regression one-vs-all (taking max output) with softmax regression on the same multi-class problem. I would expect the performance to be quite similar. Neither model copes well with non-linear relationships between input and target classes.