用八種編程語(yǔ)言來(lái)找出最長(zhǎng)的字符串
我試圖使用最快的算法來(lái)在每種語(yǔ)言中完成任務(wù)要求，如果你找到了更好的方案眨攘，請(qǐng)告訴我一下。
給定一個(gè)字符串str嚣州，找到不重復(fù)字符的最長(zhǎng)子字符串鲫售。
比如我們有 “ABDEFGABEF”, 最長(zhǎng)的字符串是 “BDEFGA” 和 “DEFGAB”, 長(zhǎng)度為6.
再如 “BBBB” 最長(zhǎng)字符串是 “B”, 長(zhǎng)度為1.
再比如 “neatcoding” 最長(zhǎng)字符串是“neatcodi”, 長(zhǎng)度為8.
所需的時(shí)間復(fù)雜度為O（n），其中n是字符串的長(zhǎng)度该肴。
我們將逐個(gè)字符地遍歷該字符串
檢查此字符是否在當(dāng)前子字符串中情竹，如果是，則將當(dāng)前子字符串保存到子字符串集合中匀哄，使用此字符作為起始值創(chuàng)建一個(gè)新的子字符串秦效；
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 如果否，則將此字符添加到當(dāng)前子字符串中涎嚼；
至此，循環(huán)結(jié)束，檢查當(dāng)前子字符串是否為空阱冶，如果是若皱，則不執(zhí)行任何操作
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 如果否，請(qǐng)將其添加到子字符串集合
我們?cè)O(shè)置一個(gè)對(duì)象來(lái)存儲(chǔ)最長(zhǎng)的子字符串，
現(xiàn)在像樊，讓我們遍歷子字符串集合涂滴，找到最長(zhǎng)的一個(gè)
? ? 檢查當(dāng)前子字符串是否更長(zhǎng)首量，如果是觉啊，則替換最長(zhǎng)的字符串
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 如果沒(méi)有，什么也不做
最后，我們有最長(zhǎng)的子字符串。
讓我們編碼。
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>();
StringBuilder currentSub = new StringBuilder();
HashSet<char> hashChar = new HashSet<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>();
? ? ? HashSet<Character> set=new HashSet();?
? ? ? 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>()
? var currentSub = ""
? var currentSet: HashSet<Char> = HashSet()?
? 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 <set>
#include <sstream>
using namespace std;
string
returnLongestNonRepeatSubString (const string & s)
{
? ? if (s.empty ())
? ? {
? ? ? ? return "";
? ? }
? ? std::vector <string> subCollection;
? ? stringstream currentSub;
? ? set <char> currentSet;
? ? 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("ABDEFGABEF")<<std::endl;
? ? cout<<returnLongestNonRepeatSubString("BBBB")<<std::endl;
? ? cout<<returnLongestNonRepeatSubString("neatcoding")<<std::endl;
? ? 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>()
? 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"))
