用八種編程語言來找出最長的字符串
我試圖使用最快的算法來在每種語言中完成任務要求，如果你找到了更好的方案，請告訴我一下。
給定一個字符串str，找到不重複字符的最長子字符串。
比如我們有 “ABDEFGABEF”, 最長的字符串是 “BDEFGA” 和 “DEFGAB”, 長度為6.
再如 “BBBB” 最長字符串是 “B”, 長度為1.
再比如 “neatcoding” 最長字符串是“neatcodi”, 長度為8.
所需的時間複雜度為O（n），其中n是字符串的長度。
我們將逐個字符地遍歷該字符串
檢查此字符是否在當前子字符串中，如果是，則將當前子字符串保存到子字符串集合中，使用此字符作為起始值創建一個新的子字符串；
如果否，則將此字符添加到當前子字符串中；
至此，循環結束，檢查當前子字符串是否為空，如果是，則不執行任何操作
如果否，請將其添加到子字符串集合
我們設置一個對象來存儲最長的子字符串，
現在，讓我們遍歷子字符串集合，找到最長的一個
檢查當前子字符串是否更長，如果是，則替換最長的字符串
如果沒有，什麼也不做
最後，我們有最長的子字符串。
讓我們編碼。
In Javascript:
returnLongestNonRepeatSubString = (s) => {
if(!s){
return "";
}
let subCollection = [];
let currentSub = "";
let currentSet = new Set;
for(let i = 0; i < s.length; i ++) {
let c = s[i];
if(!currentSet.has(c)) {
currentSub +=c;
currentSet.add(c);
}
else {
subCollection.push(currentSub);
currentSub = [];
currentSet.clear();
currentSub = "" + c;
currentSet.add(c);
}
}
if(currentSub.length > 0){
subCollection.push(currentSub);
}
let longest = "";
for(let i = 0 ; i < subCollection.length ; i ++) {
let sub = subCollection[i];
if(sub.length > longest.length) {
longest = sub;
}
}
return longest;
}
console.log(returnLongestNonRepeatSubString("ABDEFGABEF"))
console.log(returnLongestNonRepeatSubString("BBBB"))
console.log(returnLongestNonRepeatSubString("neatcoding"))
In C#:
using System;
using System.Text;
using System.Collections.Generic;
public class NeatCoding
{
public static void Main(string[] args)
{
//Your code goes here
Console.WriteLine(returnLongestNonRepeatSubString("ABDEFGABEF"));
Console.WriteLine(returnLongestNonRepeatSubString("BBBB"));
Console.WriteLine(returnLongestNonRepeatSubString("neatcoding"));
}
static string returnLongestNonRepeatSubString(string s)
{
if (string.IsNullOrEmpty(s))
{
return "";
}
List<string> subCollection = new List<string>();/<string>/<string>
StringBuilder currentSub = new StringBuilder();
HashSet<char> hashChar = new HashSet<char>();/<char>/<char>
for (int i = 0; i < s.Length; i++)
{
char c = s[i];
if (!hashChar.Contains(c))
{
hashChar.Add(c);
currentSub.Append(c);
}
else
{
subCollection.Add(currentSub.ToString());
hashChar.Clear();
currentSub.Clear();
currentSub.Append(c);
hashChar.Add(c);
}
}
if (currentSub.Length > 0)
{
subCollection.Add(currentSub.ToString());
}
string longest = "";
for (int i = 0; i < subCollection.Count; i++)
{
string sub = subCollection[i];
if (sub.Length > longest.Length)
{
longest = sub;
}
}
return longest;
}
}
In Java:
import java.util.*;
public class NeatCoding{
public static void main(String []args){
System.out.println(returnLongestNonRepeatSubString("ABDEFGABEF"));
System.out.println(returnLongestNonRepeatSubString("BBBB"));
System.out.println(returnLongestNonRepeatSubString("neatcoding"));
}
static String returnLongestNonRepeatSubString(String s)
{
if (s == null || s.length() == 0)
{
return "";
}
List<string> subCollection = new ArrayList<string>();/<string>/<string>
HashSet<character> set=new HashSet(); /<character>
StringBuilder currentSub = new StringBuilder();
for (int i = 0; i < s.length(); i++)
{
char c = s.charAt(i);
if (!set.contains(c))
{
currentSub.append(c);
}
else
{
set.add(c);
subCollection.add(currentSub.toString());
currentSub.setLength(0);
currentSub.append(c);
}
}
if (currentSub.length() > 0)
{
subCollection.add(currentSub.toString());
}
String longest = "";
for (int i = 0; i < subCollection.size(); i++)
{
String sub = subCollection.get(i);
if (sub.length() > longest.length())
{
longest = sub;
}
}
return longest;
}
}
In Kotlin:
fun main() {
println(returnLongestNonRepeatSubString("ABDEFGABEF"))
println(returnLongestNonRepeatSubString("BBBB"))
println(returnLongestNonRepeatSubString("neatcoding"))
}
fun returnLongestNonRepeatSubString(s: String?): String {
if (s == null || s.length == 0) {
return ""
}
val subCollection = ArrayList<string>()/<string>
var currentSub = ""
var currentSet: HashSet<char> = HashSet() /<char>
for (i in 0 until s.length) {
val c = s[i]
if (!currentSet.contains(c)) {
currentSub += c
currentSet.add(c)
} else {
subCollection.add(currentSub)
currentSub = "" + c
currentSet.clear()
currentSet.add(c)
}
}
if (currentSub.length > 0) {
subCollection.add(currentSub)
}
var longest = ""
for (i in subCollection.indices) {
val sub = subCollection[i]
if (sub.length > longest.length) {
longest = sub
}
}
return longest
}
In Golang:
package main
import (
"fmt"
"bytes"
)
func main() {
fmt.Println(returnLongestNonRepeatSubString("ABDEFGABEF"))
fmt.Println(returnLongestNonRepeatSubString("BBBB"))
fmt.Println(returnLongestNonRepeatSubString("neatcoding"))
}
func returnLongestNonRepeatSubString(s string) string {
if len(s) == 0 {
return ""
}
var subCollection []string
var currentSub bytes.Buffer
currentMap := map[byte]bool{}
for i := 0; i < len(s); i++ {
var c = s[i]
_, ok := currentMap[c]
if !ok {
currentSub.WriteByte(c)
currentMap[c] = true
} else {
subCollection = append(subCollection, currentSub.String())
currentSub .Reset()
currentSub.WriteByte(c)
currentMap = map[byte]bool{}
currentMap[c] = true
}
}
if currentSub.Len() > 0 {
subCollection = append(subCollection, currentSub.String())
}
var longest = ""
for _, sub := range subCollection {
if len(sub) > len(longest) {
longest = sub
}
}
return longest
}
In c++:
#include <iostream>
#include <vector>
#include
#include <sstream>
using namespace std;
string
returnLongestNonRepeatSubString (const string & s)
{
if (s.empty ())
{
return "";
}
std::vector <string> subCollection;/<string>
stringstream currentSub;
set <char> currentSet;/<char>
for (int i = 0; i < s.length (); i++)
{
char c = s[i];
if (currentSet.find (c) == currentSet.end())
{
currentSub << c;
currentSet.insert(c);
}
else
{
subCollection.push_back (currentSub.str());
currentSub.clear();
currentSub << c;
currentSet.clear();
currentSet.insert(c);
}
}
if( currentSub.gcount() > 0)
{
subCollection.push_back (currentSub.str());
}
string longest = "";
for (int i = 0; i < subCollection.size(); i++)
{
string sub = subCollection.at(i);
if (sub.length() > longest.length())
{
longest = sub;
}
}
return longest;
}
int main()
{
cout<<returnlongestnonrepeatsubstring>
cout<<returnlongestnonrepeatsubstring>
cout<<returnlongestnonrepeatsubstring>
return 0;
}
In Python:
def returnLongestNonRepeatSubString(s):
if not s:
return ""
subCollection = []
currentSub = []
currentSet = set()
for c in s:
if (c not in currentSet):
currentSet.add(c)
currentSub.append(c)
else:
subCollection.append(''.join(currentSub))
currentSub = [c]
currentSet.clear()
currentSet.add(c)
if len(currentSub) > 0:
subCollection.append(''.join(currentSub))
longest = ""
for sub in subCollection:
if (len(sub) > len(longest)):
longest = sub
return longest
print(returnLongestNonRepeatSubString("ABDEFGABEF"))
print(returnLongestNonRepeatSubString("BBBB"))
print(returnLongestNonRepeatSubString("neatcoding"))
In Swift:
import Foundation
func returnLongestNonRepeatSubString (s: String) -> String {
if (s == nil || s.isEmpty) {
return ""
}
var subCollection = [String]()
var currentSub = ""
var currentSet = Set<character>()/<character>
for c in s {
currentSet.contains(c)
if !currentSet.contains(c) {
currentSet.insert(c)
currentSub.append(c)
}
else {
subCollection.append(currentSub);
currentSet = []
currentSub = String(c)
currentSet.insert(c)
}
}
if currentSub.count > 0 {
subCollection.append(currentSub);
}
var longest = ""
for sub in subCollection {
if sub.length > longest.length {
longest = sub
}
}
return longest
}
print(returnLongestNonRepeatSubString(s: "ABDEFGABEF"))
print(returnLongestNonRepeatSubString(s: "BBBB"))
print(returnLongestNonRepeatSubString(s: "neatcoding"))
/<returnlongestnonrepeatsubstring>/<returnlongestnonrepeatsubstring>/<returnlongestnonrepeatsubstring>閱讀更多 丁哥開講 的文章
關鍵字: 編程語言 JavaScript 算法
